原题
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1] ]
解法
思想
做这道题的时候我才发现我做这类回溯算法的题还是蛮少的,对集合的深克隆api不是很熟悉。主要是深克隆的蛮麻烦 -。-||
思想就是回溯啦,可以用一个数组记录使用过了的元素。
代码
class Solution {
List<List<Integer>> ans = new ArrayList<>();
int[] globalNums;
public List<List<Integer>> permute(int[] nums) {
int[] used = new int[nums.length];
globalNums = nums;
List<Integer> list = new ArrayList<>();
trackback(list,used,0);
return ans;
}
public void trackback(List<Integer> list,int[] used,int usedCount){
if(usedCount==globalNums.length){
ans.add(list);
}
for(int i = 0;i<globalNums.length;i++){
if(used[i]==0){
List<Integer> copy = new ArrayList<>(list);
copy.add(globalNums[i]);
int[] usedCopy = Arrays.copyOf(used,used.length);
usedCopy[i] = 1;
trackback(copy,usedCopy,usedCount+1);
}
}
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode46-%e5%85%a8%e6%8e%92%e5%88%97/