回溯法實戰：5 題用同一個模板打通 Backtracking（LC 78/39/46/79/51）

回溯（Backtracking）看起來題型很多（子集、排列、組合、棋盤……），但其實全部共用一個模板：

選擇（choose）→ 遞迴探索（explore）→ 撤銷（un-choose）

也就是「做一個選擇 → 往下走 → 回來把選擇收回 → 換下一個選擇」。差別只在兩件事：① 選擇空間怎麼定（要不要 start index、要不要 used 陣列），② 怎麼剪枝（提早停掉不可能的分支）。把這個模板焊進肌肉記憶，回溯題就只是換參數。

延續一貫的完整推導流程：

📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼

子集（78）→ 組合總和（39）→ 排列（46）→ 單字搜尋（79）→ N 皇后（51）

🧭 通用模板

def backtrack(path, choices):
    if 滿足結束條件:
        res.append(path[:])      # 收集答案（記得複製）
        return
    for choice in choices:
        if 不合法: continue       # 剪枝
        path.append(choice)      # 選擇
        backtrack(path, 新choices)# 遞迴
        path.pop()               # 撤銷

① LC 78 — Subsets

📋 題目：給定不重複的整數陣列 nums，回傳所有可能的子集（冪集），不可有重複子集。

範例：nums = [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

🌐 EN — Given an integer array nums of unique elements, return all possible subsets (the power set); no duplicate subsets. Example: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

🧭 從讀題到解法

拆解：每個元素都有「選 / 不選」兩種——這是 2ⁿ 個組合，天然的回溯/遞迴樹。
關鍵洞察：用 start index 控制「只能往後選」，避免 [1,2] 和 [2,1] 這種重複。每走到一個節點，當前 path 本身就是一個合法子集（所以無條件收集，不用等到葉節點）。
最優解：回溯，遞迴前收集當前 path。

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])                 # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)          # i+1: no reuse, only go forward
            path.pop()                      # undo
    backtrack(0, [])
    return res

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);                     // collect every node
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);   // i+1: forward only
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res; vector<int> path;
    backtrack(nums, 0, path, res);
    return res;
}

複雜度：時間 O(n · 2ⁿ)（2ⁿ 個子集，每個複製 O(n)），空間 O(n) 遞迴深度。
坑：① start index 是避免重複組合的關鍵；② 收集時要 path[:]（複製），否則存的是會被後續修改的同一個 reference；③ 子集題「每個節點都是答案」，排列題才要等到葉節點。

② LC 39 — Combination Sum

📋 題目：給定無重複正整數陣列 candidates 與目標 target，找出所有和為 target 的組合。同一個數字可重複使用。

範例：candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

🌐 EN — Given an array of distinct positive integers candidates and a target, return all combinations summing to target. The same number may be reused. Example: candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

🧭 從讀題到解法

拆解：又是組合，但可重複用同一個數。差別在遞迴時 start index 要怎麼傳。
關鍵洞察：① 因為可重複用，遞迴時傳 i（不是 i+1），讓同一個數能再被選；② 但仍要從 start 開始（不回頭），避免 [2,3] 和 [3,2] 重複；③ 剪枝：remain < 0 直接 return。
最優解：回溯，target 當作遞減的 remain。

def combinationSum(candidates, target):
    res = []
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:]); return
        if remain < 0:                          # prune
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])   # i: reusable
            path.pop()
    backtrack(0, [], target)
    return res

void backtrack(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain == 0) { res.push_back(path); return; }
    if (remain < 0) return;                      // prune
    for (int i = start; i < (int)c.size(); i++) {
        path.push_back(c[i]);
        backtrack(c, i, remain - c[i], path, res);   // i: reusable
        path.pop_back();
    }
}

複雜度：時間視解的數量而定（指數級），空間 O(target / min) 遞迴深度。
坑：① 可重複用 → 傳 i；不可重複 → 傳 i+1（這是組合題的分水嶺）；② 仍要 start index 避免順序重複；③ 進階 LC 40（每個只能用一次 + 有重複數字）要先排序再「同層去重」。

③ LC 46 — Permutations

📋 題目：給定不重複的整數陣列 nums，回傳所有可能的排列。

範例：nums = [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

🌐 EN — Given an array nums of distinct integers, return all possible permutations. Example: [1,2,3] → 6 permutations

🧭 從讀題到解法

拆解：排列在乎順序（[1,2] ≠ [2,1]），所以不能用 start index——每個位置都能放任何「還沒用過」的數。
關鍵洞察：改用 used 布林陣列標記哪些數已在當前 path 裡；每層從頭掃所有數，跳過已用的。到葉節點（path 滿）才收集。
最優解：回溯 + used 陣列。

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):              # leaf: collect
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]:                         # skip used
                continue
            used[i] = True; path.append(nums[i])
            backtrack(path, used)
            path.pop(); used[i] = False         # undo both
    backtrack([], [False] * len(nums))
    return res

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
    if (path.size() == nums.size()) { res.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true; path.push_back(nums[i]);
        backtrack(nums, path, used, res);
        path.pop_back(); used[i] = false;       // undo both
    }
}

複雜度：時間 O(n · n!)，空間 O(n)。
坑：① 排列不用 start index（要全位置都能放），用 used 陣列；② 撤銷時 path.pop() 和 used[i]=False 兩個都要還原；③ 有重複數字的 LC 47 要先排序 + 「同層相同值且前一個沒用過則跳過」。

④ LC 79 — Word Search

📋 題目：給定字元網格 board 與字串 word，判斷 word 能否由網格中相鄰（上下左右）字元連成，同一格不可重複用。

範例：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" → true

🌐 EN — Given a character grid board and a string word, return whether word can be formed from adjacent (4-directional) cells, with no cell reused. Example: word = "ABCCED" → true

🧭 從讀題到解法

拆解：在網格上「沿著相鄰格走出一個字串」——這是網格上的回溯（DFS），每格可往四方向延伸。
關鍵洞察：從每個格子當起點 DFS；比對到第 i 個字元時，往四方向找第 i+1 個。走過的格暫時標記（防重複用），回溯時還原。
最優解：對每格啟動 DFS，匹配 word 逐字元。

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):                      # matched all
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        board[r][c] = '#'                       # mark visited
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = word[i]                   # undo (restore)
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
    if (i == (int)word.size()) return true;
    int rows = board.size(), cols = board[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i]) return false;
    char tmp = board[r][c];
    board[r][c] = '#';                          // mark visited
    bool found = dfs(board, word, r+1, c, i+1) || dfs(board, word, r-1, c, i+1)
              || dfs(board, word, r, c+1, i+1) || dfs(board, word, r, c-1, i+1);
    board[r][c] = tmp;                          // restore
    return found;
}
bool exist(vector<vector<char>>& board, string word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}

複雜度：時間 O(m·n·4^L)（L 為 word 長度），空間 O(L) 遞迴。
坑：① 走過的格要標記（如改成 #），探索完還原——這就是回溯的「撤銷」；② 邊界與字元不符的判斷寫在 DFS 開頭；③ 不用額外 visited 陣列，直接改 board 省空間（記得還原）。

⑤ LC 51 — N-Queens

📋 題目：在 n×n 棋盤上放 n 個皇后，使得任兩個不在同一行、列、斜線上，回傳所有擺法。

範例：n = 4 → 2 種解

🌐 EN — Place n queens on an n×n board so no two share a row, column, or diagonal; return all solutions. Example: n = 4 → 2 solutions

🧭 從讀題到解法

拆解：逐行放皇后（每行剛好一個），決定這行放哪一列。是經典的「帶約束的回溯」。
關鍵洞察（O(1) 衝突判斷）：用三個集合記「被佔用的列、主對角線（r−c）、副對角線（r+c）」——放之前 O(1) 查衝突，剪掉非法分支。同對角線的特徵：r−c 相同（主）、r+c 相同（副）。
最優解：逐行回溯 + 三個集合剪枝。

def solveNQueens(n):
    res = []
    cols, diag1, diag2 = set(), set(), set()    # column, r-c, r+c
    board = [['.'] * n for _ in range(n)]
    def backtrack(r):
        if r == n:
            res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue                        # prune conflicts
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            board[r][c] = 'Q'
            backtrack(r + 1)
            board[r][c] = '.'                   # undo all
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
    backtrack(0)
    return res

int N;
vector<vector<string>> res;
vector<bool> cols, d1, d2;                       // d1: r-c+N-1, d2: r+c
vector<string> board;
void backtrack(int r) {
    if (r == N) { res.push_back(board); return; }
    for (int c = 0; c < N; c++) {
        if (cols[c] || d1[r - c + N - 1] || d2[r + c]) continue;   // prune
        cols[c] = d1[r - c + N - 1] = d2[r + c] = true;
        board[r][c] = 'Q';
        backtrack(r + 1);
        board[r][c] = '.';                                          // undo
        cols[c] = d1[r - c + N - 1] = d2[r + c] = false;
    }
}
vector<vector<string>> solveNQueens(int n) {
    N = n; res.clear();
    cols.assign(n, false); d1.assign(2*n, false); d2.assign(2*n, false);
    board.assign(n, string(n, '.'));
    backtrack(0);
    return res;
}

複雜度：時間約 O(n!)（剪枝後遠小於 nⁿ），空間 O(n)。
坑：① 逐行放（天然保證不同行），只需查列與兩條對角線；② 對角線用 r−c（主）和 r+c（副）標識，C++ 的 r−c 要 +N−1 避免負索引；③ 撤銷時三個集合 + board 都要還原。

一張表記住全部

題	選擇空間	何時收集	關鍵 / 剪枝
LC 78 子集	start index（不回頭）	每個節點	收集要複製 path
LC 39 組合總和	start index，傳 `i`（可重複）	remain==0	remain<0 剪枝
LC 46 排列	used 陣列（全位置）	葉節點（path 滿）	撤銷還原 path + used
LC 79 單字搜尋	四方向 DFS	匹配完 word	標記走過 + 還原
LC 51 N 皇后	逐行選列	r==n	列/主副對角線集合剪枝

面試辨識口訣

看到「所有子集 / 冪集」→ start index，每個節點都收集。
看到「組合、湊出 target」→ start index；可重複傳 i，不可重複傳 i+1。
看到「所有排列、在乎順序」→ used 陣列，不用 start index。
看到「棋盤 / 網格走出某結果」→ 網格 DFS 回溯，標記走過再還原。
看到「放 N 個東西且彼此有約束」→ 逐層放 + 用集合做 O(1) 剪枝。

回溯的精髓就一句:選擇 → 遞迴 → 撤銷,而面試的關鍵是想清楚「選擇空間怎麼定(start index? used 陣列?)」與「怎麼剪枝」。模板焊死,剩下都是換參數。

回溯（Backtracking）看起來題型很多（子集、排列、組合、棋盤……），但其實全部共用一個模板：

選擇（choose）→ 遞迴探索（explore）→ 撤銷（un-choose）

延續一貫的完整推導流程：

📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼

子集（78）→ 組合總和（39）→ 排列（46）→ 單字搜尋（79）→ N 皇后（51）

🧭 通用模板

def backtrack(path, choices):
    if 滿足結束條件:
        res.append(path[:])      # 收集答案（記得複製）
        return
    for choice in choices:
        if 不合法: continue       # 剪枝
        path.append(choice)      # 選擇
        backtrack(path, 新choices)# 遞迴
        path.pop()               # 撤銷

① LC 78 — Subsets

📋 題目：給定不重複的整數陣列 nums，回傳所有可能的子集（冪集），不可有重複子集。

範例：nums = [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

🌐 EN — Given an integer array nums of unique elements, return all possible subsets (the power set); no duplicate subsets. Example: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

🧭 從讀題到解法

拆解：每個元素都有「選 / 不選」兩種——這是 2ⁿ 個組合，天然的回溯/遞迴樹。
關鍵洞察：用 start index 控制「只能往後選」，避免 [1,2] 和 [2,1] 這種重複。每走到一個節點，當前 path 本身就是一個合法子集（所以無條件收集，不用等到葉節點）。
最優解：回溯，遞迴前收集當前 path。

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])                 # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)          # i+1: no reuse, only go forward
            path.pop()                      # undo
    backtrack(0, [])
    return res

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);                     // collect every node
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);   // i+1: forward only
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res; vector<int> path;
    backtrack(nums, 0, path, res);
    return res;
}

複雜度：時間 O(n · 2ⁿ)（2ⁿ 個子集，每個複製 O(n)），空間 O(n) 遞迴深度。
坑：① start index 是避免重複組合的關鍵；② 收集時要 path[:]（複製），否則存的是會被後續修改的同一個 reference；③ 子集題「每個節點都是答案」，排列題才要等到葉節點。

② LC 39 — Combination Sum

📋 題目：給定無重複正整數陣列 candidates 與目標 target，找出所有和為 target 的組合。同一個數字可重複使用。

範例：candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

🌐 EN — Given an array of distinct positive integers candidates and a target, return all combinations summing to target. The same number may be reused. Example: candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

🧭 從讀題到解法

拆解：又是組合，但可重複用同一個數。差別在遞迴時 start index 要怎麼傳。
關鍵洞察：① 因為可重複用，遞迴時傳 i（不是 i+1），讓同一個數能再被選；② 但仍要從 start 開始（不回頭），避免 [2,3] 和 [3,2] 重複；③ 剪枝：remain < 0 直接 return。
最優解：回溯，target 當作遞減的 remain。

def combinationSum(candidates, target):
    res = []
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:]); return
        if remain < 0:                          # prune
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])   # i: reusable
            path.pop()
    backtrack(0, [], target)
    return res

void backtrack(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain == 0) { res.push_back(path); return; }
    if (remain < 0) return;                      // prune
    for (int i = start; i < (int)c.size(); i++) {
        path.push_back(c[i]);
        backtrack(c, i, remain - c[i], path, res);   // i: reusable
        path.pop_back();
    }
}

複雜度：時間視解的數量而定（指數級），空間 O(target / min) 遞迴深度。
坑：① 可重複用 → 傳 i；不可重複 → 傳 i+1（這是組合題的分水嶺）；② 仍要 start index 避免順序重複；③ 進階 LC 40（每個只能用一次 + 有重複數字）要先排序再「同層去重」。

③ LC 46 — Permutations

📋 題目：給定不重複的整數陣列 nums，回傳所有可能的排列。

範例：nums = [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

🌐 EN — Given an array nums of distinct integers, return all possible permutations. Example: [1,2,3] → 6 permutations

🧭 從讀題到解法

拆解：排列在乎順序（[1,2] ≠ [2,1]），所以不能用 start index——每個位置都能放任何「還沒用過」的數。
關鍵洞察：改用 used 布林陣列標記哪些數已在當前 path 裡；每層從頭掃所有數，跳過已用的。到葉節點（path 滿）才收集。
最優解：回溯 + used 陣列。

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):              # leaf: collect
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]:                         # skip used
                continue
            used[i] = True; path.append(nums[i])
            backtrack(path, used)
            path.pop(); used[i] = False         # undo both
    backtrack([], [False] * len(nums))
    return res

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
    if (path.size() == nums.size()) { res.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true; path.push_back(nums[i]);
        backtrack(nums, path, used, res);
        path.pop_back(); used[i] = false;       // undo both
    }
}

複雜度：時間 O(n · n!)，空間 O(n)。
坑：① 排列不用 start index（要全位置都能放），用 used 陣列；② 撤銷時 path.pop() 和 used[i]=False 兩個都要還原；③ 有重複數字的 LC 47 要先排序 + 「同層相同值且前一個沒用過則跳過」。

④ LC 79 — Word Search

📋 題目：給定字元網格 board 與字串 word，判斷 word 能否由網格中相鄰（上下左右）字元連成，同一格不可重複用。

範例：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" → true

🌐 EN — Given a character grid board and a string word, return whether word can be formed from adjacent (4-directional) cells, with no cell reused. Example: word = "ABCCED" → true

🧭 從讀題到解法

拆解：在網格上「沿著相鄰格走出一個字串」——這是網格上的回溯（DFS），每格可往四方向延伸。
關鍵洞察：從每個格子當起點 DFS；比對到第 i 個字元時，往四方向找第 i+1 個。走過的格暫時標記（防重複用），回溯時還原。
最優解：對每格啟動 DFS，匹配 word 逐字元。

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):                      # matched all
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        board[r][c] = '#'                       # mark visited
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = word[i]                   # undo (restore)
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
    if (i == (int)word.size()) return true;
    int rows = board.size(), cols = board[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i]) return false;
    char tmp = board[r][c];
    board[r][c] = '#';                          // mark visited
    bool found = dfs(board, word, r+1, c, i+1) || dfs(board, word, r-1, c, i+1)
              || dfs(board, word, r, c+1, i+1) || dfs(board, word, r, c-1, i+1);
    board[r][c] = tmp;                          // restore
    return found;
}
bool exist(vector<vector<char>>& board, string word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}

複雜度：時間 O(m·n·4^L)（L 為 word 長度），空間 O(L) 遞迴。
坑：① 走過的格要標記（如改成 #），探索完還原——這就是回溯的「撤銷」；② 邊界與字元不符的判斷寫在 DFS 開頭；③ 不用額外 visited 陣列，直接改 board 省空間（記得還原）。

⑤ LC 51 — N-Queens

📋 題目：在 n×n 棋盤上放 n 個皇后，使得任兩個不在同一行、列、斜線上，回傳所有擺法。

範例：n = 4 → 2 種解

🌐 EN — Place n queens on an n×n board so no two share a row, column, or diagonal; return all solutions. Example: n = 4 → 2 solutions

🧭 從讀題到解法

拆解：逐行放皇后（每行剛好一個），決定這行放哪一列。是經典的「帶約束的回溯」。
關鍵洞察（O(1) 衝突判斷）：用三個集合記「被佔用的列、主對角線（r−c）、副對角線（r+c）」——放之前 O(1) 查衝突，剪掉非法分支。同對角線的特徵：r−c 相同（主）、r+c 相同（副）。
最優解：逐行回溯 + 三個集合剪枝。

def solveNQueens(n):
    res = []
    cols, diag1, diag2 = set(), set(), set()    # column, r-c, r+c
    board = [['.'] * n for _ in range(n)]
    def backtrack(r):
        if r == n:
            res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue                        # prune conflicts
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            board[r][c] = 'Q'
            backtrack(r + 1)
            board[r][c] = '.'                   # undo all
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
    backtrack(0)
    return res

int N;
vector<vector<string>> res;
vector<bool> cols, d1, d2;                       // d1: r-c+N-1, d2: r+c
vector<string> board;
void backtrack(int r) {
    if (r == N) { res.push_back(board); return; }
    for (int c = 0; c < N; c++) {
        if (cols[c] || d1[r - c + N - 1] || d2[r + c]) continue;   // prune
        cols[c] = d1[r - c + N - 1] = d2[r + c] = true;
        board[r][c] = 'Q';
        backtrack(r + 1);
        board[r][c] = '.';                                          // undo
        cols[c] = d1[r - c + N - 1] = d2[r + c] = false;
    }
}
vector<vector<string>> solveNQueens(int n) {
    N = n; res.clear();
    cols.assign(n, false); d1.assign(2*n, false); d2.assign(2*n, false);
    board.assign(n, string(n, '.'));
    backtrack(0);
    return res;
}

複雜度：時間約 O(n!)（剪枝後遠小於 nⁿ），空間 O(n)。
坑：① 逐行放（天然保證不同行），只需查列與兩條對角線；② 對角線用 r−c（主）和 r+c（副）標識，C++ 的 r−c 要 +N−1 避免負索引；③ 撤銷時三個集合 + board 都要還原。

一張表記住全部

題	選擇空間	何時收集	關鍵 / 剪枝
LC 78 子集	start index（不回頭）	每個節點	收集要複製 path
LC 39 組合總和	start index，傳 `i`（可重複）	remain==0	remain<0 剪枝
LC 46 排列	used 陣列（全位置）	葉節點（path 滿）	撤銷還原 path + used
LC 79 單字搜尋	四方向 DFS	匹配完 word	標記走過 + 還原
LC 51 N 皇后	逐行選列	r==n	列/主副對角線集合剪枝

面試辨識口訣

看到「所有子集 / 冪集」→ start index，每個節點都收集。
看到「組合、湊出 target」→ start index；可重複傳 i，不可重複傳 i+1。
看到「所有排列、在乎順序」→ used 陣列，不用 start index。
看到「棋盤 / 網格走出某結果」→ 網格 DFS 回溯，標記走過再還原。
看到「放 N 個東西且彼此有約束」→ 逐層放 + 用集合做 O(1) 剪枝。

回溯法實戰：5 題用同一個模板打通 Backtracking（LC 78/39/46/79/51）

① LC 78 — Subsets

🧭 從讀題到解法

② LC 39 — Combination Sum

🧭 從讀題到解法

③ LC 46 — Permutations

🧭 從讀題到解法

④ LC 79 — Word Search

🧭 從讀題到解法

⑤ LC 51 — N-Queens

🧭 從讀題到解法

一張表記住全部

面試辨識口訣

分享這篇文章

相關文章

行為面試 STAR #8：用一次「時間壓力下的取捨」，講好優先排序能力

鏈結串列實戰：5 題從讀題推導到最優解（LC 206/21/141/143/146）

行為面試 STAR #7：用一次「技術意見不合」，講好衝突處理與 Disagree and Commit

留言討論

回溯法實戰：5 題用同一個模板打通 Backtracking（LC 78/39/46/79/51）

① LC 78 — Subsets

🧭 從讀題到解法

② LC 39 — Combination Sum

🧭 從讀題到解法

③ LC 46 — Permutations

🧭 從讀題到解法

④ LC 79 — Word Search

🧭 從讀題到解法

⑤ LC 51 — N-Queens

🧭 從讀題到解法

一張表記住全部

面試辨識口訣

分享這篇文章

相關文章

行為面試 STAR #8：用一次「時間壓力下的取捨」，講好優先排序能力

鏈結串列實戰：5 題從讀題推導到最優解（LC 206/21/141/143/146）

行為面試 STAR #7：用一次「技術意見不合」，講好衝突處理與 Disagree and Commit

留言討論