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兩個(gè)位置元素
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的長(zhǎng)度時(shí)，結(jié)束
if (x == nums.size() - 1) {
res.add(new ArrayList<>(nums)); // 添加排列方案
return;
}
for (int i = x; i < nums.size(); i++) {
選擇，
例如x=0時(shí)，固定num[i]在第0位置;
x=0,i=0時(shí)，固定num[0]在第0個(gè)位置
x=0,i=1時(shí)，固定num[1]在第0個(gè)位置
x=0,i=2時(shí)，固定num[2]在第0個(gè)位置
x=1,i=1時(shí)，固定num[1]在第1個(gè)位置
x=1,i=2時(shí)，固定num[2]在第1個(gè)位置
swap(i, x); // 交換，將 nums[i] 固定在第 x 位
遞歸，開(kāi)始固定x+1，例如開(kāi)始固定第2位置元素
dfs(x + 1); // 開(kāi)啟固定第 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ù)雜度分析：
時(shí)間復(fù)雜度 O(N!N) ： N 為數(shù)組 nums 的長(zhǎng)度；時(shí)間復(fù)雜度和數(shù)組排列的方案數(shù)成線性關(guān)系，方案數(shù)為 N×(N?1)×(N?2)…×2×1 ，即復(fù)雜度為 O(N!) ；數(shù)組拼接操作 join() 使用 O(N) ；因此總體時(shí)間復(fù)雜度為 O(N!N) 。
空間復(fù)雜度 O(N) ： 全排列的遞歸深度為 N ，系統(tǒng)累計(jì)使用?？臻g大小為 O(N)
nums 1 2 3
index 0 1 2
dfs(0) x=0,i=0時(shí)，固定num[0]在第0個(gè)位置
dfs(1) x=1,i=1時(shí)，固定num[1]在第1個(gè)位置
dfs(2) return 123
dfs(1) x=1,i=2時(shí)，固定num[2]在第1個(gè)位置
dfs(2) return 132
dfs(0) x=0,i=1時(shí)，固定num[1]在第0個(gè)位置
dfs(1) x=1,i=1時(shí)，固定num[1]在第1個(gè)位置
dfs(2) return 213
dfs(1) x=1,i=2時(shí)，固定num[2]在第1個(gè)位置
dfs(2) return 231
dfs(0) x=0,i=2時(shí)，固定num[2]在第0個(gè)位置
dfs(1) x=1,i=1時(shí)，固定num[1]在第1個(gè)位置
dfs(2) return 321
dfs(1) x=1,i=2時(shí)，固定num[2]在第1個(gè)位置
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)
。。。
寫蒙了。。
老早之前就看過(guò)回溯，以為理解了，現(xiàn)在再看一個(gè)都不懂，說(shuō)明根本沒(méi)懂。。。
假設(shè)我們已經(jīng)填到第 first 個(gè)位置，那么 nums 數(shù)組中 [0,first?1] 是已填過(guò)的數(shù)的集合，[first,n?1] 是待填的數(shù)的集合。
我們肯定是嘗試用 [first,n?1] 里的數(shù)去填第 first 個(gè)數(shù)，假設(shè)待填的數(shù)的下標(biāo)為 i，那么填完以后我們將第 i 個(gè)數(shù)和第 first 個(gè)數(shù)交換，即能使得在填第 first+1 個(gè)數(shù)的時(shí)候 nums 數(shù)組的 [0,first] 部分為已填過(guò)的數(shù)，[first+1,n?1] 為待填的數(shù)，回溯的時(shí)候交換回來(lái)即能完成撤銷操作。
舉個(gè)簡(jiǎn)單的例子，假設(shè)我們有 [2,5,8,9,10] 這 5 個(gè)數(shù)要填入，已經(jīng)填到第 3 個(gè)位置，已經(jīng)填了 [8,9] 兩個(gè)數(shù)，那么這個(gè)數(shù)組目前為 [8,9 ∣ 2,5,10] 這樣的狀態(tài)，分隔符區(qū)分了左右兩個(gè)部分。
假設(shè)這個(gè)位置我們要填 10 這個(gè)數(shù)，為了維護(hù)數(shù)組，我們將 2 和 10 交換，即能使得數(shù)組繼續(xù)保持分隔符左邊的數(shù)已經(jīng)填過(guò)，右邊的待填 [8,9,10 ∣ 2,5] 。
image.png
