描述
给定一个数字列表，返回其所有可能的排列。
注意事项
你可以假设没有重复数字。
样例
给出列表 [1,2,2]，不同的排列有：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
挑战
使用递归和非递归分别完成该题。
代码
- 递归
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
//注意空指针和空集的区别，空指针返回[],空集返回[[]]
if (nums == null) {
return results;
}
if (nums.length == 0) {
//List是更抽象的接口类，不能用于实例化，实例化用ArrayList
results.add(new ArrayList<Integer>());
return results;
}
List<Integer> list = new ArrayList<>();
helper(nums, list, results);
return results;
}
private void helper(int[] nums,
List<Integer> list,
List<List<Integer>> results) {
//递归的出口
// 同[求子集](//www.greatytc.com/p/b494dde0ffdb)有区别，
// 子集的 startIndex 每进入一轮递归 +1，startIndex >= nums.length 则不再进入递归
if (list.size() == nums.length) {
results.add(new ArrayList<Integer>(list));
return;
}
//递归的拆解，题目声明无重复元素，所以要有一个去重的过程
for (int i = 0; i < nums.length; i++) {
if (list.contains(nums[i])) {
continue;
}
list.add(nums[i]);
helper(nums, list, results);
list.remove(list.size() - 1);
}
}
}
- 非递归
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
ArrayList<List<Integer>> permutations
= new ArrayList<List<Integer>>();
if (nums == null) {
return permutations;
}
if (nums.length == 0) {
permutations.add(new ArrayList<Integer>());
return permutations;
}
int n = nums.length;
ArrayList<Integer> stack = new ArrayList<Integer>();
stack.add(-1);
while (stack.size() != 0) {
Integer last = stack.get(stack.size() - 1);
stack.remove(stack.size() - 1);
// increase the last number
int next = -1;
for (int i = last + 1; i < n; i++) {
if (!stack.contains(i)) {
next = i;
break;
}
}
if (next == -1) {
continue;
}
// generate the next permutation
stack.add(next);
for (int i = 0; i < n; i++) {
if (!stack.contains(i)) {
stack.add(i);
}
}
// copy to permutations set
ArrayList<Integer> permutation = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
permutation.add(nums[stack.get(i)]);
}
permutations.add(permutation);
}
return permutations;
}
}
本题递归过程
DFS的关键在于理解递归在for循环中的变化过程，以本题[1, 2, 3]为例，第一个for循环时，先将1加入list，list[1],然后程序运行到helper(rst, list, nums)时进入第二层递归，for循环到1，list中有1，continue，for循环到2，把2加入list，list[1, 2],程序再次运行到helper(rst, list, nums)时进入第三层递归，for循环到1,2，list中已经存在1,2，continue，for循环到3，把3加入list，进入第四层递归，此时list.size() == num.length,将list加入rst，return语句直接退出第四层递归(注意到目前为止尽管运行了4层递归仍然没有执行过程序的最后一句),退出第四层递归后开始执行第三层递归的最后一句，从list里删除最后一个元素，此时第三层for循环已经执行到i=2，执行完list.remove(list.size() - 1)就相当于第三层递归整个结束了，退出第三层递归，此时list为[1,2]，开始执行第二层递归,此时第二层递归的i=1，for循环还没结束，执行完list.remove(list.size() - 1)后， list变成[1],for循环中i等于2，将nums[2]=3加入list，list为[1, 3],继续执行helper(rst, list, nums)，再次进入第五次递归，list中有1，continue，for循环到2(i = 1)将2加入list，进入下一层第六次递归，满足出口条件，return，本层第六次递归结束，第五次递归执行到for循环中i=1的最后一句list.remove(list.size() - 1)，从list里移除2使list从[1, 3 , 2]变回[1, 3]开始执行for循环i = 2，发现list存在3，continue，直接跳出for循环结束第五次递归重新进入第二层递归，第二递归也执行到了for循环i = 2的最后一句，执行list.remove(list.size() - 1)将list变成[1]后，退出第二层递归，开始执行第一层递归的for循环中i = 0的最后一句list.remove(list.size() - 1)将list变成空集，然后执行for循环i =1，list变成[2]之后执行递归list变成[2,1]，递归[2,1,3]接下来过程和之前描述过程类似
总结
本题和子集问题基本上是一个套路，细节上就在于本题没有定义一个startIndex来限制循环的起始位置，也就实现了排列的目的
