算法思路：
Leetcode 046的题目。这里作为知识点归纳。
- 类似于组合题，但用到了visited数组且递归中从i=0开始。
应用：
- 找所有可能性
注意事项：
- 每一种排列加入到结果集时要复制path。
学习要点：
详见DFS要点，大部分DFS题目涉及
- 用到全组合的API: dfs(nums, start, path, result), 4个参数
- 用到全组合的递归: dfs(nums, i + 1, path, result)
- 用到全排列的其他部分包括恢复状态和终止条件(加入res)
Leetcode 046 Permutations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return [[]]
path, res = [], []
self.dfs(nums, set(), path, res)
return res
def dfs(self, nums, visited, path, res):
if len(path) == len(nums):
res.append(list(path))
return
for i in range(len(nums)):
if i in visited:
continue
visited.add(i)
path.append(nums[i])
self.dfs(nums, visited, path, res)
path.pop()
visited.remove(i)
|
Java代码：
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
| public List<List<Integer>> permute(int[] nums) {
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
if(nums == null) {
return res;
}
dfs(nums, new HashSet<>(), path, res);
return res;
}
void dfs(int[] nums, Set<Integer> visited, List<Integer> path, List<List<Integer>> res) {
if(path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++) {
if(visited.contains(i))
continue;
visited.add(i);
path.add(nums[i]);
dfs(nums, visited, path, res);
visited.remove(i);
path.remove(path.size() - 1);
}
}
|
算法分析：
时间复杂度为O(n*n!)，空间复杂度O(1)。解大小乘以path长度
