image.png
image.png
image.png
回溯
DFS 深度優(yōu)先搜索
算法框架：
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
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);
}
深度優(yōu)先搜索：回溯
void dfs(int x) {
x=nums的長度時，結(jié)束
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); // 恢復(fù)交換
}
}
public List<List<Integer>> permute(int[] nums) {
this.res = new ArrayList<>();
this.nums = new ArrayList<>();
數(shù)組轉(zhuǎn)列表
for (int num : nums) {
this.nums.add(num);
}
dfs(0);
return res;
}
}
復(fù)雜度分析：
時間復(fù)雜度 O(N!N) ： N 為數(shù)組 nums 的長度；時間復(fù)雜度和數(shù)組排列的方案數(shù)成線性關(guān)系失仁，方案數(shù)為 N×(N?1)×(N?2)…×2×1 尸曼，即復(fù)雜度為 O(N!) ；數(shù)組拼接操作 join() 使用 O(N) 萄焦；因此總體時間復(fù)雜度為 O(N!N) 控轿。
空間復(fù)雜度 O(N) ： 全排列的遞歸深度為 N ，系統(tǒng)累計使用椃鞣猓空間大小為 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)
私沮。始赎。。
寫蒙了仔燕。造垛。
老早之前就看過回溯，以為理解了晰搀，現(xiàn)在再看一個都不懂五辽，說明根本沒懂。厕隧。奔脐。
假設(shè)我們已經(jīng)填到第 first 個位置，那么 nums 數(shù)組中 [0,first?1] 是已填過的數(shù)的集合吁讨，[first,n?1] 是待填的數(shù)的集合髓迎。
我們肯定是嘗試用 [first,n?1] 里的數(shù)去填第 first 個數(shù)，假設(shè)待填的數(shù)的下標(biāo)為 i建丧，那么填完以后我們將第 i 個數(shù)和第 first 個數(shù)交換排龄，即能使得在填第 first+1 個數(shù)的時候 nums 數(shù)組的 [0,first] 部分為已填過的數(shù)，[first+1,n?1] 為待填的數(shù)翎朱，回溯的時候交換回來即能完成撤銷操作橄维。
舉個簡單的例子，假設(shè)我們有 [2,5,8,9,10] 這 5 個數(shù)要填入拴曲，已經(jīng)填到第 3 個位置争舞，已經(jīng)填了 [8,9] 兩個數(shù)，那么這個數(shù)組目前為 [8,9 ∣ 2,5,10] 這樣的狀態(tài)澈灼，分隔符區(qū)分了左右兩個部分竞川。
假設(shè)這個位置我們要填 10 這個數(shù)店溢，為了維護數(shù)組，我們將 2 和 10 交換委乌，即能使得數(shù)組繼續(xù)保持分隔符左邊的數(shù)已經(jīng)填過床牧，右邊的待填 [8,9,10 ∣ 2,5] 。
image.png
