回溯算法八题通关：从子集到 N 皇后（Python + C++）

回溯算法本质是暴力穷举，通过“选择、探索、撤销”来遍历所有可能解。本文整理了8道经典回溯题目，每道题包含：题目描述、解题思路、图解（文本示意）、Python代码、C++代码、复杂度分析。掌握这些，回溯类题目基本通关。

---

📌 题目清单

题号	题目	核心考点
78	子集	回溯 / 枚举（每个元素选或不选）
46	全排列	回溯 + 标记数组
39	组合总和	回溯 + 可重复选取（排序剪枝）
40	组合总和 II	回溯 + 去重（同层跳过）
77	组合	回溯（C(n,k)）
17	电话号码的字母组合	回溯（映射 + 递归）
51	N 皇后	回溯 + 列/对角线判断
200	岛屿数量	DFS / BFS（也可归为图）

注：岛屿数量虽通常归为图/DFS，但核心思想与回溯相通，故一并收录。

---

1. 子集（LeetCode 78）

题目描述

给定一个整数数组 nums，数组中的元素互不相同，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

示例：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解题思路

• 方法一：回溯（选或不选）：对每个元素决定是否加入当前子集，递归遍历所有可能性。
• 方法二：枚举长度：依次枚举子集长度，用回溯生成定长子集。
• 常用写法：回溯时用 start 指针控制当前可选的起始位置，避免重复组合。

图解（回溯，start 法）

nums = [1,2,3]
递归树：
[]
├─ 选1 → [1]
│   ├─ 选2 → [1,2]
│   │   └─ 选3 → [1,2,3]
│   └─ 选3 → [1,3]
├─ 选2 → [2]
│   └─ 选3 → [2,3]
└─ 选3 → [3]
共 2^3 = 8 个子集

Python代码

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])  # 收集当前子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

C++代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(0, nums, path, res);
        return res;
    }
    void backtrack(int start, vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtrack(i + 1, nums, path, res);
            path.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：O(n × 2ⁿ)，共 2ⁿ 个子集，每个子集复制需 O(n)。
• 空间复杂度：O(n × 2ⁿ)（输出空间） + O(n)（递归栈）。

---

2. 全排列（LeetCode 46）

题目描述

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解题思路

• 回溯 + 标记数组：用 used 布尔数组记录哪些元素已被使用。
• 在每一层尝试所有未被使用的元素，添加后递归，回溯时取消标记。

图解

nums = [1,2,3]
递归树（部分）：
[]
├─ 选1 → [1]
│   ├─ 选2 → [1,2]
│   │   └─ 选3 → [1,2,3]
│   └─ 选3 → [1,3]
│       └─ 选2 → [1,3,2]
├─ 选2 → [2] ...
└─ 选3 → [3] ...
共 3! = 6 种

Python代码

def permute(nums):
    res = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False
    backtrack([])
    return res

C++代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, path, used, res);
        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 < nums.size(); ++i) {
            if (!used[i]) {
                used[i] = true;
                path.push_back(nums[i]);
                backtrack(nums, path, used, res);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};

复杂度分析

• 时间复杂度：O(n × n!)，共 n! 个排列，每个复制 O(n)。
• 空间复杂度：O(n × n!)（输出） + O(n)（递归栈 + used）。

---

3. 组合总和（LeetCode 39）

题目描述

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出所有可以使数字和为 target 的组合。同一个数字可以无限制重复被选取。

示例：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解题思路

• 回溯 + 可重复选取：因为可重复，递归时 start 仍然从当前索引开始（而不是 i+1）。
• 排序后剪枝：如果当前元素已经大于剩余 target，则可提前终止循环。

图解

candidates=[2,3,6,7], target=7
递归：
[]
├─ 选2(剩余5) → [2]
│   ├─ 选2(剩余3) → [2,2]
│   │   ├─ 选2(剩余1) → 剩余1<2，剪枝
│   │   ├─ 选3(剩余0) → [2,2,3] 加入结果
│   │   └─ 选6(剩余-3) 剪枝
│   ├─ 选3(剩余2) → [2,3] -> 再选2(剩余0) → [2,3,2] 但已大于？实际需注意顺序，使用start保证不重复组合
│   └─ 选6(剩余-1) 剪枝
├─ 选3(剩余4) → [3]
│   └─ 选3(剩余1) → [3,3] -> 剩余1<3 剪枝
└─ 选7(剩余0) → [7] 加入

Python代码

def combinationSum(candidates, target):
    res = []
    candidates.sort()
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])  # 注意 i 不变，可重复使用
            path.pop()
    backtrack(0, [], target)
    return res

C++代码

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(0, candidates, target, path, res);
        return res;
    }
    void backtrack(int start, vector<int>& candidates, int remain, vector<int>& path, vector<vector<int>>& res) {
        if (remain == 0) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > remain) break;
            path.push_back(candidates[i]);
            backtrack(i, candidates, remain - candidates[i], path, res);
            path.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：O(2ⁿ) 量级，实际与 target 和数值有关。
• 空间复杂度：O(target / min(candidate))（递归深度） + 输出空间。

---

4. 组合总和 II（LeetCode 40）

题目描述

给定一个数组 candidates（可能有重复元素）和一个目标整数 target，找出所有使数字和为 target 的组合。每个数字在每个组合中只能使用一次，且解集不能包含重复组合。

示例：
输入：candidates = [10,1,2,7,6,1,5], target = 8
输出：[[1,1,6],[1,2,5],[1,7],[2,6]]

解题思路

• 先排序，便于剪枝和去重。
• 同一层递归中，如果当前数字与前一个相同且前一个未被使用（同一层跳过），则跳过，避免重复组合。
• 递归时 start + 1，因为每个数字只能用一次。

图解

candidates=[1,1,2,5,6,7,10]（排序后），target=8
递归：
[]
├─ 选第1个1(剩余7) → [1]
│   ├─ 选第2个1(剩余6) → [1,1]
│   │   ├─ 选2(剩余4) → [1,1,2] ? 实际超? 1+1+2=4不等8，继续
│   │   └─ ...
│   ├─ 选2(剩余5) → [1,2] -> 再选5(剩余0) → [1,2,5] 加入
│   └─ 选5(剩余2) → [1,5] -> 再选2(剩余0) → [1,5,2] 但顺序需保持start，实际用i+1，会得到[1,5]后再加2？注意组合无序，使用索引保证不重复。
适当剪枝即可。

Python代码

def combinationSum2(candidates, target):
    res = []
    candidates.sort()
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break
            # 同层去重：如果当前元素与前一个相同，且前一个未被使用（此处通过i>start判断）
            if i > start and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, path, remain - candidates[i])
            path.pop()
    backtrack(0, [], target)
    return res

C++代码

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(0, candidates, target, path, res);
        return res;
    }
    void backtrack(int start, vector<int>& candidates, int remain, vector<int>& path, vector<vector<int>>& res) {
        if (remain == 0) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > remain) break;
            if (i > start && candidates[i] == candidates[i-1]) continue;
            path.push_back(candidates[i]);
            backtrack(i + 1, candidates, remain - candidates[i], path, res);
            path.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：O(2ⁿ) 最坏。
• 空间复杂度：O(n) 递归栈 + 输出空间。

---

5. 组合（LeetCode 77）

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

示例：
输入：n = 4, k = 2
输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

解题思路

• 回溯，每次从 start 开始选，递归深度为 k。
• 剪枝：如果剩余可选的数字不够凑满 k，提前终止（i <= n - (k - len(path)) + 1）。

图解

n=4,k=2
递归树：
[]
├─ 选1 → [1]
│   ├─ 选2 → [1,2]
│   ├─ 选3 → [1,3]
│   └─ 选4 → [1,4]
├─ 选2 → [2]
│   ├─ 选3 → [2,3]
│   └─ 选4 → [2,4]
└─ 选3 → [3]
    └─ 选4 → [3,4]

Python代码

def combine(n, k):
    res = []
    def backtrack(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        # 剪枝：最多需要 k - len(path) 个数，所以 i 最大为 n - (k - len(path)) + 1
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return res

C++代码

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(1, n, k, path, res);
        return res;
    }
    void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& res) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
            path.push_back(i);
            backtrack(i + 1, n, k, path, res);
            path.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：O(C(n,k) × k)，共 C(n,k) 个组合，每个复制 O(k)。
• 空间复杂度：O(k)（递归栈） + 输出空间。

---

6. 电话号码的字母组合（LeetCode 17）

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键相同。

示例：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解题思路

• 建立数字到字母的映射表。
• 回溯：递归处理每个数字，对当前数字对应的每个字母进行选择，继续处理下一个数字。

图解

digits = "23"
映射: 2->abc, 3->def
递归树：
""
├─ a
│   ├─ ad, ae, af
├─ b
│   ├─ bd, be, bf
└─ c
    ├─ cd, ce, cf

Python代码

def letterCombinations(digits):
    if not digits:
        return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    res = []
    def backtrack(idx, path):
        if idx == len(digits):
            res.append(''.join(path))
            return
        for ch in mapping[digits[idx]]:
            path.append(ch)
            backtrack(idx + 1, path)
            path.pop()
    backtrack(0, [])
    return res

C++代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> res;
        string path;
        backtrack(0, digits, mapping, path, res);
        return res;
    }
    void backtrack(int idx, string& digits, vector<string>& mapping, string& path, vector<string>& res) {
        if (idx == digits.size()) {
            res.push_back(path);
            return;
        }
        int num = digits[idx] - '0';
        for (char ch : mapping[num]) {
            path.push_back(ch);
            backtrack(idx + 1, digits, mapping, path, res);
            path.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：O(3ⁿ × 4ᵐ)，其中 n 为对应3个字母的数字个数，m 为对应4个字母的数字个数。
• 空间复杂度：O(总组合数 × 长度) + O(递归深度)。

---

7. N 皇后（LeetCode 51）

题目描述

在 n×n 的棋盘上放置 n 个皇后，使得它们不能互相攻击（即任意两个皇后不同行、不同列、不同对角线）。返回所有合法的布局。

示例：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解题思路

• 按行回溯，每行尝试在某一列放置皇后。
• 需要验证该列、主对角线（行-列常数）、副对角线（行+列常数）是否已有皇后。
• 使用三个集合记录已占用的列、主对角线、副对角线。

图解

n=4，一种解法：
0: . Q . .
1: . . . Q
2: Q . . .
3: . . Q .

Python代码

def solveNQueens(n):
    res = []
    col = set()
    diag1 = set()  # r - c
    diag2 = set()  # 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 col or (r - c) in diag1 or (r + c) in diag2:
                continue
            col.add(c)
            diag1.add(r - c)
            diag2.add(r + c)
            board[r][c] = 'Q'
            backtrack(r + 1)
            board[r][c] = '.'
            col.remove(c)
            diag1.remove(r - c)
            diag2.remove(r + c)

    backtrack(0)
    return res

C++代码

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        unordered_set<int> col, diag1, diag2;
        backtrack(0, n, board, col, diag1, diag2, res);
        return res;
    }
    void backtrack(int r, int n, vector<string>& board, unordered_set<int>& col,
                   unordered_set<int>& diag1, unordered_set<int>& diag2, vector<vector<string>>& res) {
        if (r == n) {
            res.push_back(board);
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (col.count(c) || diag1.count(r - c) || diag2.count(r + c)) continue;
            col.insert(c);
            diag1.insert(r - c);
            diag2.insert(r + c);
            board[r][c] = 'Q';
            backtrack(r + 1, n, board, col, diag1, diag2, res);
            board[r][c] = '.';
            col.erase(c);
            diag1.erase(r - c);
            diag2.erase(r + c);
        }
    }
};

复杂度分析

• 时间复杂度：O(n!)，但实际小于。
• 空间复杂度：O(n)（递归栈 + 集合）。

---

8. 岛屿数量（LeetCode 200）

题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿被水包围，且通过水平或垂直方向相邻。

示例：
输入：

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3

解题思路

• DFS / BFS：遍历每个格子，遇到陆地 '1' 则岛屿数加1，并用 DFS/BFS 将与之相邻的所有陆地标记为 '0'（或使用 visited 集合），避免重复计数。

图解

遍历 (0,0) 发现 '1' → 岛屿+1，DFS 淹没相邻陆地：
(0,0),(0,1),(1,0),(1,1) 变为 '0'
继续遍历到 (2,2) 发现 '1' → 岛屿+1，淹没 (2,2)
继续到 (3,3) 发现 '1' → 岛屿+1，淹没 (3,3),(3,4)
结果 3

Python代码（DFS）

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # 标记为已访问
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

C++代码（DFS）

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size(), cols = grid[0].size();
        int count = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs(grid, r+1, c, rows, cols);
        dfs(grid, r-1, c, rows, cols);
        dfs(grid, r, c+1, rows, cols);
        dfs(grid, r, c-1, rows, cols);
    }
};

复杂度分析

• 时间复杂度：O(m × n)，每个格子最多访问一次。
• 空间复杂度：O(m × n)（最坏递归深度）。

---

🎯 总结

题目	核心技巧	时间复杂度	空间复杂度
78. 子集	start 参数，选或不选	O(n×2ⁿ)	O(n×2ⁿ)
46. 全排列	used 标记数组	O(n×n!)	O(n×n!)
39. 组合总和	可重复选取，i 不变	O(2ⁿ)	O(target/min)
40. 组合总和 II	排序 + 同层去重	O(2ⁿ)	O(n)
77. 组合	剪枝（剩余可选数）	O(C(n,k)×k)	O(k)
17. 电话号码	映射 + 递归	O(3ⁿ×4ᵐ)	O(总组合数)
51. N 皇后	列/对角线判重	O(n!)	O(n)
200. 岛屿数量	DFS/BFS 淹没	O(m×n)	O(m×n)

回溯算法的核心是“选择-递归-撤销”。关键在于明确：递归参数（如 start、used、remain）、终止条件、剪枝策略和去重方法。多画递归树，能有效避免 bug。