T46. Permutations【Medium】
题目
给出不同的数字的集合,返回所有可能的排列组合。
例如,
[1,2,3] 有如下的排列组合:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路
这题比较明显是要用到递归,只要会递归,思路就是正常小孩子就知道的思路:
排列组合(1 2 3)
= 1 + 排列组合(2 3)∪ 2 + 排列组合(1 3)∪ 3 + 排列组合(1 2)
排列组合(2 3)
= 2 + 排列组合(3)∪ 3 + 排列组合(2)
= 23 ∪ 32
可以看出在数字只有一个的时候到了递归的终点
然后看代码就好了~
代码
代码取自 Top Solution,稍作注释
public class Solution {
public List<List<Integer>> permute(int[] nums) {
//建立要返回的数据形式
List<List<Integer>> list = new ArrayList<List<Integer>>();
//开始递归
backtrack(list, new ArrayList<Integer>(), nums);
return list;
}
//主要算法:递归
public void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums){
if(tempList.size() == nums.length){
//若所有元素都用到了则加到 ArrayList 里面
list.add(new ArrayList<Integer>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
//如果已经有了这个元素,则跳过这次循环
if(tempList.contains(nums[i])) continue;
//下面三步一起看,用到了递归
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
网友评论