LeetCode-44 回溯解法
全排列：一篇看懂回溯解法
题目
给定一个不含重复数字的整数数组nums，返回它的所有全排列。
示例
输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]一、题目
这道题的核心是：
把数组中的每个数字，都轮流放到当前位置上，直到所有位置都放满。
比如nums = [1,2,3]：
- 第一位可以放
1 - 第一位也可以放
2 - 第一位还可以放
3
每确定一位，就继续递归处理下一位。
这就是典型的回溯问题。
二、最容易想到的思路
可以这样理解：
- 先确定第
0个位置放谁 - 再确定第
1个位置放谁 - 再确定第
2个位置放谁 - 当所有位置都确定后，就得到一个排列
为了高效，我们通常使用交换的方式，而不是每次都新建数组。
三、回溯解法
代码
importjava.util.ArrayList;importjava.util.List;classSolution{publicList<List<Integer>>permute(int[]nums){List<List<Integer>>res=newArrayList<>();backtrack(nums,0,res);returnres;}privatevoidbacktrack(int[]nums,intfirst,List<List<Integer>>res){if(first==nums.length){List<Integer>list=newArrayList<>();for(intnum:nums){list.add(num);}res.add(list);return;}for(inti=first;i<nums.length;i++){swap(nums,first,i);// 选择一个数放到当前位置backtrack(nums,first+1,res);// 递归处理下一个位置swap(nums,first,i);// 恢复现场}}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}四、为什么这样做可行
假设数组是：
[1,2,3]第一步：确定第 0 位
- 把
1放到第 0 位，数组还是[1,2,3] - 把
2放到第 0 位，数组变成[2,1,3] - 把
3放到第 0 位，数组变成[3,2,1]
第二步：递归确定后面的位
例如已经确定第 0 位是1，那后面就去处理[2,3]的排列。
最后会得到：
[1,2,3][1,3,2]
再继续处理第 0 位是2、第 0 位是3的情况。
五、为什么交换后还要交换回来
这是回溯最关键的一步。
例如当前数组是：
[1,2,3]当我们尝试把2放到第 0 位时，会执行：
swap(nums,0,1)数组变成：
[2,1,3]递归处理完以后，如果不换回来，数组就一直是[2,1,3]，会影响后面继续尝试别的情况。
所以必须再交换一次：
swap(nums,0,1)把数组恢复成原来的样子：
[1,2,3]这样下一轮尝试才不会出错。
一句话概括：
交换过去是做选择，交换回来是撤销选择。
六、执行过程示例
以nums = [1,2,3]为例：
第一层：确定第 0 位
- 选
1，得到[1,2,3] - 选
2，得到[2,1,3] - 选
3，得到[3,2,1]
第二层：确定第 1 位
例如当前是[1,2,3]：
- 选
2，得到[1,2,3] - 选
3，得到[1,3,2]
第三层：确定第 2 位
只剩最后一个数，直接加入结果。
最终得到全部 6 种排列。
七、复杂度分析
时间复杂度
O(n × n!)原因：
- 一共有
n!种排列 - 每次加入答案时，需要把当前数组复制到结果中，花费
O(n)
空间复杂度
O(n)主要是递归调用栈的深度。
不计最终答案所占空间。
八、这道题的本质
这道题的本质不是“交换”，而是：
枚举每个位置可以放哪些数。
交换只是一个实现手段，它的优点是：
- 不需要额外创建很多新数组
- 代码更简洁
- 性能更好
九、总结
这道题是经典的回溯题。
可以记住下面这个模板：
做选择 递归 撤销选择对应到本题就是：
swap(nums,first,i);backtrack(nums,first+1,res);swap(nums,first,i);其中：
swap：把一个数放到当前的位置backtrack：递归处理下一个位置- 再
swap：恢复现场，继续尝试别的数
十、结论
全排列问题最经典的解法就是回溯 + 交换。
它的核心思想是：
- 每一层确定一个位置放什么
- 通过交换把候选数字放到当前位置
- 递归处理剩余位置
- 处理完再恢复原数组