📝个人主页：五敷有你
🔥系列专栏：算法分析与设计
⛺️稳中求进，晒太阳
题目
给定一个不含重复数字的整数数组
nums，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
思路
- 回溯
这个问题可以看作是n个排列成一行的空格，我们需要从左向右填入给定的n个数，每个只能使用一次，那么很直接的可以想到穷举法，从左向右依次填入，看能不能填完这个n个空格，在这个过程可以使用回溯来模拟。
我们定义一个backtrack(first,output)表示从左向右填到first个位置，当前排列为output,那么整个递归函数分为两个情况：
一、first==n
这个情况就表示已经填完了n个位置，可以进行一次排列的收集
二、first<n
这个情况是从第一个格到first是固定了，之后就
之后first左边的固定了，右边的还在回溯。
first现在指向2，之后2和2自己进行交换，有人可能回想为什么2还要与自己进行交换，因为1 2 3 4 5 6 本身也是一种排列，难道不是吗？呼
然后first指向3，同理，自身与自身交换一次，然后一直回溯，。。。。
之后再回来回溯交换
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}代码实现：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有数都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
}
}
运行结果
