46.全排列
程序员文章站
2022-07-08 15:56:52
...
1.题目
2.解法
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> aList = new LinkedList();
ArrayList<Integer> true_nums = new ArrayList<Integer>();
for (int i : nums) {
true_nums.add(i);
}
int len = nums.length;
backtrack(0, len, true_nums, aList);
return aList;
}
public void backtrack(int first, int len, ArrayList<Integer> nums,
List<List<Integer>> aList) {
if (first == len) {
aList.add(new ArrayList<Integer>(nums));}
for (int i = first; i < len; i++) {
Collections.swap(nums, first, i);
backtrack(first+1, len, nums, aList);
Collections.swap(nums, first, i);
}
}
}
==时间复杂度空间复杂度O(n!)
3.思考
这里是使用的回溯方法
1、当first==n时回溯结束 (终止条件)
2、nums数组中没有swap函数,所以为了方便运算,将nums放到ArrayList中
3、我不太理解List<List> aList = new LinkedList()可以作为引用,全局使用,
nums作为ArrayList,可以在每次回溯时随意改变,难道不会影响原值嘛。