leetcode 46. 全排列
题目：46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），用flag标记nums已中使用的元素，每次搜索按顺序选取一个未被标记的元素加入排列集合，当排列集合满时，将排列集合加入结果集中，本次搜索结束，将元素标记、当前排列集合复原，进行下一次搜索。
运行数据：执行用时：1 ms，内存消耗：39.9 MB
复杂度分析：
- 时间复杂度：O(n * n!)，n为需要排列的元素个数，O(n!)为递归的时间复杂度，将结果加入结果集的时间复杂度为O(n)。
- 空间复杂度：O(n)，n为需要排列的元素个数，递归栈的深度为n。
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
|
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
boolean[] flag = new boolean[nums.length];
backtracking(result, nums, flag, new ArrayList<>());
return result;
}
private void backtracking(List<List<Integer>> result, int[] nums, boolean[] flag, List<Integer> permuteList) {
if (permuteList.size()== nums.length) {
result.add(new ArrayList<>(permuteList));
return ;
}
for (int i = 0; i < nums.length; i++) {
if (flag[i]) {
continue;
}
flag[i] = true;
permuteList.add(nums[i]);
backtracking(result, nums, flag, permuteList);
permuteList.remove(permuteList.size() - 1);
flag[i] = false;
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
