Description#
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
nums are unique.
Solutions#
Solution 1: DFS (Backtracking)#
We design a function $dfs(i)$ to represent that the first $i$ positions have been filled, and now we need to fill the $i+1$ position. We enumerate all possible numbers, if this number has not been filled, we fill in this number, and then continue to fill the next position, until all positions are filled.
The time complexity is $O(n \times n!)$, where $n$ is the length of the array. There are $n!$ permutations in total, and each permutation takes $O(n)$ time to construct.
Similar problems:
1
2
3
| class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(permutations(nums))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private boolean[] vis;
private int[] nums;
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
vis = new boolean[nums.length];
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
for (int j = 0; j < nums.length; ++j) {
if (!vis[j]) {
vis[j] = true;
t.add(nums[j]);
dfs(i + 1);
t.remove(t.size() - 1);
vis[j] = false;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
vector<int> t(n);
vector<bool> vis(n);
function<void(int)> dfs = [&](int i) {
if (i == n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t[i] = nums[j];
dfs(i + 1);
vis[j] = false;
}
}
};
dfs(0);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func permute(nums []int) (ans [][]int) {
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(t))
return
}
for j, v := range nums {
if !vis[j] {
vis[j] = true
t[i] = v
dfs(i + 1)
vis[j] = false
}
}
}
dfs(0)
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function permute(nums: number[]): number[][] {
const n = nums.length;
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...nums]);
}
for (let j = i; j < n; j++) {
[nums[i], nums[j]] = [nums[j], nums[i]];
dfs(i + 1);
[nums[i], nums[j]] = [nums[j], nums[i]];
}
};
dfs(0);
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| impl Solution {
fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
let n = nums.len();
if i == n {
res.push(nums.clone());
return;
}
for j in i..n {
nums.swap(i, j);
Self::dfs(i + 1, nums, res);
nums.swap(i, j);
}
}
pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(0, &mut nums, &mut res);
res
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| /**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
const ans = [];
const t = [];
const vis = new Array(n).fill(false);
function dfs(i) {
if (i >= n) {
ans.push([...t]);
return;
}
for (let j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t.push(nums[j]);
dfs(i + 1);
vis[j] = false;
t.pop();
}
}
}
dfs(0);
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class Solution {
public IList<IList<int>> Permute(int[] nums) {
var ans = new List<IList<int>>();
var t = new List<int>();
var vis = new bool[nums.Length];
dfs(nums, 0, t, vis, ans);
return ans;
}
private void dfs(int[] nums, int i, IList<int> t, bool[] vis, IList<IList<int>> ans) {
if (i >= nums.Length) {
ans.Add(new List<int>(t));
return;
}
for (int j = 0; j < nums.Length; ++j) {
if (!vis[j]) {
vis[j] = true;
t.Add(nums[j]);
dfs(nums, i + 1, t, vis, ans);
t.RemoveAt(t.Count - 1);
vis[j] = false;
}
}
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
if i == n:
ans.append(t[:])
return
for j in range(n):
if not vis[j]:
vis[j] = True
t[i] = nums[j]
dfs(i + 1)
vis[j] = False
n = len(nums)
vis = [False] * n
t = [0] * n
ans = []
dfs(0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| impl Solution {
#[allow(dead_code)]
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ret = Vec::new();
let mut cur_vec = Vec::new();
let mut vis = vec![false; nums.len() + 1];
Self::dfs(&nums, &mut vis, 0, &mut cur_vec, &mut ret);
ret
}
#[allow(dead_code)]
fn dfs(
nums: &Vec<i32>,
vis: &mut Vec<bool>,
index: i32,
cur_vec: &mut Vec<i32>,
ans: &mut Vec<Vec<i32>>
) {
let n = nums.len();
if (index as usize) == n {
ans.push(cur_vec.clone());
return;
}
// Otherwise, let's iterate the nums vector
for i in 0..n {
if !vis[i] {
// If this number hasn't been visited, then visit it
vis[i] = true;
cur_vec.push(nums[i]);
Self::dfs(nums, vis, index + 1, cur_vec, ans);
// Reset the changes
cur_vec.pop().unwrap();
vis[i] = false;
}
}
}
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
nonlocal mask
if i == n:
ans.append(t[:])
return
for j in range(n):
if (mask >> j & 1) == 0:
mask |= 1 << j
t[i] = nums[j]
dfs(i + 1)
mask ^= 1 << j
n = len(nums)
mask = 0
t = [0] * n
ans = []
dfs(0)
return ans
|
