题目描述
Given a collection of distinct integers, return all possible permutations.
给出一个不重复的数字的集合，返回所有可能的排列。
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
思路分析
典型的DFS的方式解决，重要的是在于理解如何组合出来不同的全排列。有两种思路：
一种是高中数学学过的A33全排列的方法，如下图所示，从第一个格子开始依次填空，第一个空可以填1或2或3，当填完第一个格子后，第二个格子只剩下两种选择，当填完第二个格子后，第三个格子只剩下一种选择。
A33依次填空
另一个种是通过交换的方法来实现，需要理解这样一个概念，设123的全排列为permute(1,2,3)，那么
permute(1,2,3) = 1,permute(2,3) + 2,permute(1,3) + 3,permute(1,2)
permute(2,3) = 2,permute(3) + 3,permute(2) = 2,3 + 3,2
...
那么可以得到123的全排列如图，DFS树的每一层负责定死全排列的每一位，例如第二层通过数组元素交换负责定死第一位为1或2或3，然后再递归到下一层去求后面的全排列。
交换的递归过程
代码实现
第二种思路的实现代码如下。
/**
* 25 / 25 test cases passed.
* Status: Accepted
* Runtime: 5 ms
*
* @param nums
* @return
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
recursivePermute(nums, 0, result);
return result;
}
private void recursivePermute(int[] nums, int pos, List<List<Integer>> result) {
if (pos > nums.length - 1) {
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
temp.add(nums[i]);
}
result.add(temp);
return;
}
for (int i = pos; i < nums.length; i++) {
swap(nums, pos, i);
recursivePermute(nums, pos + 1, result);
swap(nums, pos, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
