image.png
image.png
image.png
回溯
DFS 深度优先搜索
算法框架：
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
class Solution {
List<Integer> nums;
List<List<Integer>> res;
交互a,b两个位置元素
void swap(int a, int b) {
int tmp = nums.get(a);
nums.set(a, nums.get(b));
nums.set(b, tmp);
}
深度优先搜索：回溯
void dfs(int x) {
x=nums的长度时，结束
if (x == nums.size() - 1) {
res.add(new ArrayList<>(nums)); // 添加排列方案
return;
}
for (int i = x; i < nums.size(); i++) {
选择，
例如x=0时，固定num[i]在第0位置;
x=0,i=0时，固定num[0]在第0个位置
x=0,i=1时，固定num[1]在第0个位置
x=0,i=2时，固定num[2]在第0个位置
x=1,i=1时，固定num[1]在第1个位置
x=1,i=2时，固定num[2]在第1个位置
swap(i, x); // 交换，将 nums[i] 固定在第 x 位
递归，开始固定x+1，例如开始固定第2位置元素
dfs(x + 1); // 开启固定第 x + 1 位元素
撤销选择
swap(i, x); // 恢复交换
}
}
public List<List<Integer>> permute(int[] nums) {
this.res = new ArrayList<>();
this.nums = new ArrayList<>();
数组转列表
for (int num : nums) {
this.nums.add(num);
}
dfs(0);
return res;
}
}
复杂度分析：
时间复杂度 O(N!N) ： N 为数组 nums 的长度；时间复杂度和数组排列的方案数成线性关系，方案数为 N×(N−1)×(N−2)…×2×1 ，即复杂度为 O(N!) ；数组拼接操作 join() 使用 O(N) ；因此总体时间复杂度为 O(N!N) 。
空间复杂度 O(N) ： 全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N)
nums 1 2 3
index 0 1 2
dfs(0) x=0,i=0时，固定num[0]在第0个位置
dfs(1) x=1,i=1时，固定num[1]在第1个位置
dfs(2) return 123
dfs(1) x=1,i=2时，固定num[2]在第1个位置
dfs(2) return 132
dfs(0) x=0,i=1时，固定num[1]在第0个位置
dfs(1) x=1,i=1时，固定num[1]在第1个位置
dfs(2) return 213
dfs(1) x=1,i=2时，固定num[2]在第1个位置
dfs(2) return 231
dfs(0) x=0,i=2时，固定num[2]在第0个位置
dfs(1) x=1,i=1时，固定num[1]在第1个位置
dfs(2) return 321
dfs(1) x=1,i=2时，固定num[2]在第1个位置
dfs(2) return 312
dfs(x) i=x
dfs(0) 0| i=0
dfs(1) 0 1| i=1
dfs(2) return i=2 1，2，3
撤销选择 swap(1,1)
i++ i=2
选择 swap(2,1)
dfs(2) return 1，3，2
撤销选择 swap(2,1) 1，2，3
dfs(1) 撤销选择 swap(1,1)
i++ i = 2
选择 swap(2,1) 1，3，2
dfs(2) return 2，1，3
撤销选择 swap(2,1) 2，3，1
dfs(0) 撤销选择 swap(0,0)
i++ i=1
选择 swap(1,0) 2，1，3
dfs(1)
选择 swap(1,1)
dfs(2) return
撤销选择 swap(1,1)
i++ i=2
选择 swap(2,2)
i++ i=2
选择 swap(2,0) 3，1，2
dfs(2) return 3，1，2
撤销选择 swap(2,0)
。。。
写蒙了。。
老早之前就看过回溯，以为理解了，现在再看一个都不懂，说明根本没懂。。。
假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合。
我们肯定是尝试用 [first,n−1] 里的数去填第 first 个数，假设待填的数的下标为 i，那么填完以后我们将第 i 个数和第 first 个数交换，即能使得在填第 first+1 个数的时候 nums 数组的 [0,first] 部分为已填过的数，[first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
举个简单的例子，假设我们有 [2,5,8,9,10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8,9] 两个数，那么这个数组目前为 [8,9 ∣ 2,5,10] 这样的状态，分隔符区分了左右两个部分。
假设这个位置我们要填 10 这个数，为了维护数组，我们将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8,9,10 ∣ 2,5] 。
image.png
