问题：
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
大意：
给出一个不同数字的集合，返回所有可能的排列。
比如：
[1,2,3] 有下面这些排列：[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路：
这就是中学时排列组合的题目，要极尽所有排列，我们就要从第一个位置开始所有的元素都有可能放一遍，第二个位置在放了第一个位置的数字后剩下的数字又都可能放一遍，第三个位置也是类似，一直到最后一个位置。
对于这种操作用递归最合适，在我们创建的函数中对于第i个位置，每个当前还剩下的数字都去尝试放一次，并且继续往下递归，最后就会得到所有可能的排列。
要注意的一点就是在递归中我们的List和数组都要进行深拷贝然后添加元素，否则不同的放置方式操作的都是同一个List或者数组，没有意义。
代码（Java）：
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
for (int i = 0; i < nums.length; i++) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
int[] hasUsed = new int[nums.length];
hasUsed[i] = 1;
doPermute(nums, resList, list, hasUsed);
}
return resList;
}
public void doPermute(int[] nums, List<List<Integer>> resList, List<Integer> list, int[] hasUsed) {
if (list.size() == nums.length) {
resList.add(list);
return;
}
for (int i = 0; i < nums.length; i++) {
if (hasUsed[i] == 0) {
List<Integer> newList = new ArrayList<Integer>();
newList.addAll(list);
newList.add(nums[i]);
int[] newUsed = hasUsed.clone();
newUsed[i] = 1;
doPermute(nums, resList, newList, newUsed);
}
}
}
}
合集：https://github.com/Cloudox/LeetCode-Record
