给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法一：
全排列问题，还是用递归 DFS 来求解。这里我们需要用到一个 visited 数组来标记某个数字是否访问过，没有访问过则添加进 out 中，直到 level 等于数组长度。注意添加元素之后要进行复原。
//全排列
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
List<Integer> out = new ArrayList<>();
int[] visited = new int[nums.length];
permuteDFS(nums, 0, visited, out, lists);
return lists;
}
public void permuteDFS(int[] nums, int level, int[] visited, List<Integer> out, List<List<Integer>> lists) {
if (level == nums.length) {
lists.add(out);
} else {
for (int i = 0; i < nums.length; i++) {
List<Integer> list;
if (visited[i] == 0) {
visited[i] = 1;
out.add(nums[i]);
list = new ArrayList<>(out);
//System.out.println(out);
permuteDFS(nums, level + 1, visited, list, lists);
out.remove(out.size() - 1);
visited[i] = 0;
}
}
}
}
打印递归过程如下：
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
[2, 3]
[2, 3, 1]
[3]
[3, 1]
[3, 1, 2]
[3, 2]
[3, 2, 1]
解法二：
还有一种递归的写法，更简单一些，每次交换 nums[] 里面的两个数字，经过递归可以生成所有的排列情况。
//全排列
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
permuteDFS(nums, 0, lists);
return lists;
}
public void permuteDFS(int[] nums, int start, List<List<Integer>> lists) {
if (start >= nums.length) {
List<Integer> list = new ArrayList<>();
for (int i : nums) {
list.add(i);
}
lists.add(list);
}
for (int i = start; i < nums.length; i++) {
//System.out.println("before: " + Arrays.toString(nums) + " start: " + start + " i: " + i);
swap(nums, start, i);
//System.out.println("swap: " + Arrays.toString(nums) + " start: " + start + " i: " + i);
permuteDFS2(nums, start + 1, lists);
swap(nums, start, i);
//System.out.println("rollback: " + Arrays.toString(nums) + " start: " + start + " i: " + i);
}
}
private void swap(int[] nums, int start, int i) {
int temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
}
打印递归过程如下：
before: [1, 2, 3] start: 0 i: 0
swap: [1, 2, 3] start: 0 i: 0
before: [1, 2, 3] start: 1 i: 1
swap: [1, 2, 3] start: 1 i: 1
before: [1, 2, 3] start: 2 i: 2
swap: [1, 2, 3] start: 2 i: 2
rollback: [1, 2, 3] start: 2 i: 2
rollback: [1, 2, 3] start: 1 i: 1
before: [1, 2, 3] start: 1 i: 2
swap: [1, 3, 2] start: 1 i: 2
before: [1, 3, 2] start: 2 i: 2
swap: [1, 3, 2] start: 2 i: 2
rollback: [1, 3, 2] start: 2 i: 2
rollback: [1, 2, 3] start: 1 i: 2
rollback: [1, 2, 3] start: 0 i: 0
before: [1, 2, 3] start: 0 i: 1
swap: [2, 1, 3] start: 0 i: 1
before: [2, 1, 3] start: 1 i: 1
swap: [2, 1, 3] start: 1 i: 1
before: [2, 1, 3] start: 2 i: 2
swap: [2, 1, 3] start: 2 i: 2
rollback: [2, 1, 3] start: 2 i: 2
rollback: [2, 1, 3] start: 1 i: 1
before: [2, 1, 3] start: 1 i: 2
swap: [2, 3, 1] start: 1 i: 2
before: [2, 3, 1] start: 2 i: 2
swap: [2, 3, 1] start: 2 i: 2
rollback: [2, 3, 1] start: 2 i: 2
rollback: [2, 1, 3] start: 1 i: 2
rollback: [1, 2, 3] start: 0 i: 1
before: [1, 2, 3] start: 0 i: 2
swap: [3, 2, 1] start: 0 i: 2
before: [3, 2, 1] start: 1 i: 1
swap: [3, 2, 1] start: 1 i: 1
before: [3, 2, 1] start: 2 i: 2
swap: [3, 2, 1] start: 2 i: 2
rollback: [3, 2, 1] start: 2 i: 2
rollback: [3, 2, 1] start: 1 i: 1
before: [3, 2, 1] start: 1 i: 2
swap: [3, 1, 2] start: 1 i: 2
before: [3, 1, 2] start: 2 i: 2
swap: [3, 1, 2] start: 2 i: 2
rollback: [3, 1, 2] start: 2 i: 2
rollback: [3, 2, 1] start: 1 i: 2
rollback: [1, 2, 3] start: 0 i: 2
解法三：
这种方法是 CareerCup 书上的方法，也挺不错的，这道题是思想是这样的：
当 n = 1 时，数组中只有一个数 a1，其全排列只有一种，即为 a1；
当 n = 2 时，数组中此时有 a1a2，其全排列有两种，a1a2 和 a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在 a1 的前后两个位置分别加入了 a2；
当 n = 3 时，数组中有 a1a2a3，此时全排列有六种，分别为 a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在 a1a2 和 a2a1 的基础上在不同的位置上加入 a3 而得到的。
c++ 代码如下，Java 代码日后补上。
_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3
_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
if (num.empty()) return vector<vector<int> >(1, vector<int>());
vector<vector<int> > res;
int first = num[0];
num.erase(num.begin());
vector<vector<int> > words = permute(num);
for (auto &a : words) {
for (int i = 0; i <= a.size(); ++i) {
a.insert(a.begin() + i, first);
res.push_back(a);
a.erase(a.begin() + i);
}
}
return res;
}
};
