回溯算法:从决策树到剪枝优化的完整LeetCode通关指南

假设你需要生成数组 [1, 2, 3] 的所有排列。最直观的想法是写三重循环，每一层选择一个不同的元素——但如果数组长度是 10 呢？你需要写 10 层嵌套循环。更糟糕的是，如果数组长度不固定呢？

回溯算法为这类问题提供了一个优雅的通用解法：用递归模拟多层循环，在每一步做出选择，探索所有可能，并在需要时撤销选择、回退状态。这种"试错-回退"的模式，让它成为解决排列、组合、子集、棋盘问题等组合优化问题的核心技术。

回溯算法的本质

回溯（Backtracking）是一种通过探索所有可能解来解决问题的算法技术。它的核心思想非常朴素：从一条路往前走，能进则进，不能进则退。

1950年代，美国数学家 D. H. Lehmer 首次使用"backtrack"一词描述这种搜索策略。此后，这门技术在约束满足问题、组合优化问题中得到了广泛应用。1972年，Niklaus Wirth 在其著作《算法+数据结构=程序》中将回溯形式化为一种系统性的问题求解方法。

回溯算法可以被形式化地理解为在状态空间树上进行深度优先搜索（DFS）。树的每个节点代表问题求解过程中的一个状态，从根节点到叶子节点的路径代表一个完整的候选解。当发现某条路径无法得到有效解时，算法会"回溯"到上一个节点，尝试其他分支。

回溯算法状态空间树

图片来源: labuladong 的算法小抄

回溯算法与普通 DFS 的关键区别在于剪枝。DFS 会遍历整棵树，而回溯会在探索过程中主动放弃那些明显不可能得到有效解的分支，从而大幅减少搜索空间。

三个核心操作

回溯算法的每一次递归调用都包含三个核心操作：

1. 做选择：将当前候选元素加入路径，更新状态。

2. 递归探索：基于当前状态继续向下探索。

3. 撤销选择：将之前的选择从路径中移除，恢复状态，为下一次选择做准备。

这三个步骤构成了回溯算法的基本框架。用伪代码表示：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }
}

这个框架之所以强大，是因为它将复杂的组合问题分解为简单的"选择-探索-撤销"循环。每一层递归只需要考虑当前状态下的所有可能选择，而不需要关心之前或之后的决策。

LeetCode 回溯算法题目全景

回溯算法在 LeetCode 上有大量经典题目，可以按照问题类型分为以下几类：

类型	题目编号	题目名称
排列	46	Permutations
排列	47	Permutations II
组合	77	Combinations
组合	39	Combination Sum
组合	40	Combination Sum II
组合	216	Combination Sum III
子集	78	Subsets
子集	90	Subsets II
棋盘	51	N-Queens
棋盘	52	N-Queens II
棋盘	37	Sudoku Solver
字符串	17	Letter Combinations of a Phone Number
字符串	22	Generate Parentheses
字符串	93	Restore IP Addresses
字符串	131	Palindrome Partitioning
搜索	79	Word Search
其他	494	Target Sum
其他	784	Letter Case Permutation

接下来，我们将逐一分析这些经典题目，并提供完整的 Java 实现。

排列问题：元素顺序有影响

排列问题的特点是：从 n 个元素中选出 n 个，顺序不同则结果不同。比如 [1, 2, 3] 的全排列包含 [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。

LeetCode 46. Permutations

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

解题思路：每一层递归决定当前位置放哪个元素。为了保证每个元素只使用一次，需要维护一个 used 数组记录哪些元素已被选择。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }
    
    private void backtrack(int[] nums, List<Integer> path, 
                           boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;  // 剪枝：跳过已使用的元素
            
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, path, used, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

复杂度分析：

时间复杂度：$O(n \times n!)$，共有 $n!$ 种排列，每种排列需要 $O(n)$ 时间复制到结果中。
空间复杂度：$O(n)$，递归深度最大为 $n$。

LeetCode 47. Permutations II

题目描述：给定一个可包含重复数字的数组，返回所有不重复的全排列。

解题思路：与上一题的区别在于数组中有重复元素，需要额外的剪枝来避免生成重复排列。关键技巧是先排序，然后在同一层递归中跳过与上一个元素相同的候选。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);  // 排序是去重的前提
        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, result);
        return result;
    }
    
    private void backtrack(int[] nums, List<Integer> path, 
                           boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // 剪枝：如果当前元素与前一个相同，且前一个未被使用（说明是同一层）
            // 则跳过，避免重复排列
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, path, used, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

去重逻辑解析：!used[i - 1] 的含义是：前一个相同元素在本层递归中刚刚被撤销选择，说明它是"同一层"的前一个选择。如果此时再选择当前元素，就会产生与之前相同的排列。

组合问题：元素顺序无关

组合问题与排列问题的核心区别在于：组合只关心选了哪些元素，不关心顺序。比如 [1, 2] 和 [2, 1] 是同一个组合。

LeetCode 77. Combinations

题目描述：给定整数 n 和 k，返回 1 到 n 中所有可能的 k 个数的组合。

解题思路：为了避免重复，我们需要保证每次选择时只考虑比上一个选择更大的元素。这就是通过 startIndex 参数实现的"向前看"策略。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int n, int k, int start, 
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        // 剪枝优化：如果剩余可选元素不足，提前终止
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtrack(n, k, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

剪枝优化：循环上界从 n 改为 n - (k - path.size()) + 1。原理是：如果还需要选 k - path.size() 个元素，但剩余可选元素只有 n - i + 1 个，当后者小于前者时，可以直接跳过。

LeetCode 39. Combination Sum

题目描述：给定无重复元素的数组 candidates 和目标值 target，找出所有和为 target 的组合。同一数字可以重复选取。

解题思路：与上一题类似，但由于可以重复选取，递归时的起始索引不再是 i + 1，而是 i（允许再次选择当前元素）。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;  // 剪枝：和已超过目标
        
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            // 注意：这里传 i 而不是 i + 1，因为可以重复选取
            backtrack(candidates, target - candidates[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 40. Combination Sum II

题目描述：给定可能包含重复元素的数组 candidates 和目标值 target，找出所有和为 target 的组合。每个数字只能使用一次。

解题思路：结合了"去重"和"组合"两个要点。先排序，然后在同一层递归中跳过重复元素。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            // 剪枝：跳过同层重复元素
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            // 剪枝：如果当前元素已超过剩余目标，后面的更大元素更不可能
            if (candidates[i] > target) break;
            
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 216. Combination Sum III

题目描述：找出所有相加之和为 n 的 k 个数的组合，数字范围 1-9，每个数字最多使用一次。

解题思路：这是组合问题的简化版本，候选集固定为 1-9。

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(k, n, 1, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int k, int n, int start, 
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k && n == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (path.size() >= k || n <= 0) return;
        
        for (int i = start; i <= 9; i++) {
            path.add(i);
            backtrack(k, n - i, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

子集问题：枚举所有可能

子集问题要求生成数组的所有子集，包括空集。从决策树的角度看，子集问题与组合问题的区别在于：子集问题在每个节点都要收集结果，而组合问题只在叶子节点收集。

LeetCode 78. Subsets

题目描述：给定不含重复元素的整数数组，返回所有可能的子集。

解题思路：每一层递归决定是否选择当前元素。注意在每个节点（包括根节点）都要将当前路径加入结果。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] nums, int start, 
                           List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));  // 在每个节点收集结果
        
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度：$O(n \times 2^n)$。共有 $2^n$ 个子集，每个子集需要 $O(n)$ 时间复制。

LeetCode 90. Subsets II

题目描述：给定可能包含重复元素的整数数组，返回所有可能的子集（不能有重复子集）。

解题思路：排序 + 同层去重。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] nums, int start, 
                           List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;  // 去重
            
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

棋盘问题：约束满足的典型

棋盘问题是回溯算法的经典应用场景，特点是需要在放置元素时检查多个约束条件。

LeetCode 51. N-Queens

题目描述：在 n×n 的棋盘上放置 n 个皇后，使其不能互相攻击。返回所有可能的放置方案。

解题思路：逐行放置皇后，每次放置时检查列、主对角线、副对角线是否已有皇后。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(board, 0, result);
        return result;
    }
    
    private void backtrack(char[][] board, int row, List<List<String>> result) {
        if (row == board.length) {
            result.add(constructBoard(board));
            return;
        }
        
        for (int col = 0; col < board.length; col++) {
            if (!isValid(board, row, col)) continue;  // 剪枝
            
            board[row][col] = 'Q';
            backtrack(board, row + 1, result);
            board[row][col] = '.';  // 撤销选择
        }
    }
    
    private boolean isValid(char[][] board, int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    
    private List<String> constructBoard(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }
}

优化技巧：可以用三个布尔数组分别记录已占用的列、主对角线、副对角线，将 isValid 检查降到 $O(1)$。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1];  // row - col + n - 1
        boolean[] diag2 = new boolean[2 * n - 1];  // row + col
        
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        
        backtrack(board, 0, cols, diag1, diag2, result);
        return result;
    }
    
    private void backtrack(char[][] board, int row, boolean[] cols, 
                           boolean[] diag1, boolean[] diag2, 
                           List<List<String>> result) {
        if (row == board.length) {
            result.add(constructBoard(board));
            return;
        }
        
        for (int col = 0; col < board.length; col++) {
            int d1 = row - col + board.length - 1;
            int d2 = row + col;
            
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;
            board[row][col] = 'Q';
            
            backtrack(board, row + 1, cols, diag1, diag2, result);
            
            board[row][col] = '.';
            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }
    
    private List<String> constructBoard(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }
}

LeetCode 37. Sudoku Solver

题目描述：解数独谜题。

解题思路：遍历每个空格，尝试填入 1-9，检查是否满足数独规则（行、列、3×3 宫格内无重复）。

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board);
    }
    
    private boolean backtrack(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') continue;
                
                for (char c = '1'; c <= '9'; c++) {
                    if (!isValid(board, row, col, c)) continue;
                    
                    board[row][col] = c;
                    if (backtrack(board)) return true;  // 找到解立即返回
                    board[row][col] = '.';  // 回溯
                }
                return false;  // 1-9 都不行，无解
            }
        }
        return true;  // 所有格子都填满了
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c) return false;  // 检查行
            if (board[i][col] == c) return false;  // 检查列
            // 检查 3x3 宫格
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }
}

字符串问题：分割与匹配

字符串相关的回溯问题通常涉及字符串的分割、匹配或生成。

LeetCode 17. Letter Combinations of a Phone Number

题目描述：给定数字字符串，返回所有可能的字母组合（电话号码对应字母）。

解题思路：每个数字对应多个字母，问题转化为在每一层选择一个字母，组合成所有可能的结果。

class Solution {
    private String[] mapping = {"", "", "abc", "def", "ghi", "jkl", 
                                "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) return result;
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }
    
    private void backtrack(String digits, int index, 
                           StringBuilder path, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        
        String letters = mapping[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, index + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

LeetCode 22. Generate Parentheses

题目描述：生成所有有效的括号组合。

解题思路：在任意位置，左括号数量必须大于等于右括号数量。利用这个约束进行剪枝。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), 0, 0, n, result);
        return result;
    }
    
    private void backtrack(StringBuilder path, int open, int close, 
                           int n, List<String> result) {
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }
        
        if (open < n) {  // 还可以放左括号
            path.append('(');
            backtrack(path, open + 1, close, n, result);
            path.deleteCharAt(path.length() - 1);
        }
        if (close < open) {  // 右括号数量必须小于左括号
            path.append(')');
            backtrack(path, open, close + 1, n, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

LeetCode 93. Restore IP Addresses

题目描述：从数字字符串恢复所有可能的 IP 地址。

解题思路：IP 地址分为 4 段，每段 1-3 位数字，值在 0-255 之间。不能有前导零（除非是单独的 0）。

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(String s, int start, List<String> path, 
                           List<String> result) {
        if (path.size() == 4) {
            if (start == s.length()) {
                result.add(String.join(".", path));
            }
            return;
        }
        
        for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
            String segment = s.substring(start, start + len);
            // 剪枝：检查有效性
            if (segment.length() > 1 && segment.charAt(0) == '0') continue;
            if (Integer.parseInt(segment) > 255) continue;
            
            path.add(segment);
            backtrack(s, start + len, path, result);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 131. Palindrome Partitioning

题目描述：将字符串分割成若干回文子串，返回所有可能的分割方案。

解题思路：在每一步尝试所有可能的分割点，检查分割出的子串是否是回文。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(String s, int start, List<String> path, 
                           List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int end = start; end < s.length(); end++) {
            if (!isPalindrome(s, start, end)) continue;  // 剪枝
            
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

LeetCode 79. Word Search

题目描述：在二维网格中搜索单词是否存在。

解题思路：从每个位置开始 DFS，向四个方向探索。需要标记已访问位置以避免重复使用。

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean backtrack(char[][] board, String word, 
                              int row, int col, int index) {
        if (index == word.length()) return true;
        if (row < 0 || row >= board.length || 
            col < 0 || col >= board[0].length ||
            board[row][col] != word.charAt(index)) {
            return false;
        }
        
        char temp = board[row][col];
        board[row][col] = '#';  // 标记已访问
        
        boolean found = backtrack(board, word, row + 1, col, index + 1) ||
                        backtrack(board, word, row - 1, col, index + 1) ||
                        backtrack(board, word, row, col + 1, index + 1) ||
                        backtrack(board, word, row, col - 1, index + 1);
        
        board[row][col] = temp;  // 恢复
        return found;
    }
}

其他经典问题

LeetCode 494. Target Sum

题目描述：在数组每个元素前添加 + 或 -，计算所有可能的表达式值等于 target 的方案数。

解题思路：每个元素有两种选择：加或减。这可以转化为子集和问题。

class Solution {
    private int count = 0;
    
    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }
    
    private void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) count++;
            return;
        }
        
        backtrack(nums, target, index + 1, sum + nums[index]);  // 选择 +
        backtrack(nums, target, index + 1, sum - nums[index]);  // 选择 -
    }
}

优化：可以转化为 0-1 背包问题，使用动态规划将时间复杂度从 $O(2^n)$ 降到 $O(n \times sum)$。

LeetCode 784. Letter Case Permutation

题目描述：将字符串中的字母转换为大小写，返回所有可能的组合。

解题思路：对于每个字母，可以选择保持原样或转换大小写。

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s.toCharArray(), 0, result);
        return result;
    }
    
    private void backtrack(char[] chars, int index, List<String> result) {
        if (index == chars.length) {
            result.add(new String(chars));
            return;
        }
        
        if (Character.isLetter(chars[index])) {
            chars[index] = Character.toLowerCase(chars[index]);
            backtrack(chars, index + 1, result);
            chars[index] = Character.toUpperCase(chars[index]);
            backtrack(chars, index + 1, result);
        } else {
            backtrack(chars, index + 1, result);
        }
    }
}

剪枝技术的艺术

回溯算法的效率很大程度上取决于剪枝的质量。好的剪枝可以将指数级的时间复杂度大幅降低。以下是几种常见的剪枝策略：

1. 约束剪枝

在状态无效时立即返回，避免无效搜索。比如在组合求和问题中，当当前和已经超过目标值时停止。

if (currentSum > target) return;  // 约束剪枝

2. 边界剪枝

当剩余选择不足以完成目标时提前终止。比如在组合问题中，如果剩余元素数量不足以凑齐 k 个，直接返回。

// 还需要选 need 个元素，剩余可选元素有 remaining 个
if (remaining < need) return;  // 边界剪枝

3. 重复剪枝

在数组有重复元素时，通过排序 + 跳过同层重复元素避免生成重复解。

if (i > start && nums[i] == nums[i - 1]) continue;  // 重复剪枝

4. 可行性剪枝

在选择之前预判该选择是否可能成功。比如在 N 皇后问题中，放置皇后前检查是否冲突。

if (!isValid(board, row, col)) continue;  // 可行性剪枝

复杂度分析与优化

回溯算法的时间复杂度通常是指数级的，但在实际应用中，有效的剪枝可以将搜索空间大幅压缩。

问题类型	时间复杂度	空间复杂度
排列	$O(n \times n!)$	$O(n)$
组合	$O(k \times C_n^k)$	$O(k)$
子集	$O(n \times 2^n)$	$O(n)$
N皇后	$O(n!)$	$O(n)$

常见优化技巧

1. 预处理：排序数组，便于去重和提前终止。

2. 状态压缩：使用位运算替代布尔数组，减少空间占用。

3. 记忆化：对于存在重叠子问题的情况，可以用 HashMap 缓存中间结果。

4. 迭代加深：当只需要一个解时，可以用迭代加深搜索（IDS）优化。

总结

回溯算法的本质是在状态空间树上进行深度优先搜索，通过"选择-探索-撤销"的模式穷举所有可能解。它的强大之处在于框架的通用性——无论是排列、组合、子集还是棋盘问题，都可以用同一套模板解决。

掌握回溯算法的关键是理解三件事：

状态表示：如何用变量表示当前搜索状态？
选择集合：在当前状态下有哪些可选操作？
剪枝条件：如何提前判断某条路径不可能得到有效解？

当这三点想清楚后，套用回溯模板就是水到渠成的事。在实际刷题中，建议从简单的子集、组合问题入手，逐步挑战 N 皇后、数独等复杂问题，体会剪枝对效率的影响。

参考资料

Wikipedia. Backtracking
GeeksforGeeks. Backtracking Algorithms
LeetCode Discuss. Backtracking algorithm + problems to practice
LeetCode Discuss. Famous Backtracking Problems
labuladong. Backtracking Algorithm to Solve All Permutation/Combination/Subset Problems
Medium. A tree-based introduction to backtracking

回溯算法的本质#

三个核心操作#

LeetCode 回溯算法题目全景#

排列问题：元素顺序有影响#

LeetCode 46. Permutations#

LeetCode 47. Permutations II#

组合问题：元素顺序无关#

LeetCode 77. Combinations#

LeetCode 39. Combination Sum#

LeetCode 40. Combination Sum II#

LeetCode 216. Combination Sum III#

子集问题：枚举所有可能#

LeetCode 78. Subsets#

LeetCode 90. Subsets II#

棋盘问题：约束满足的典型#

LeetCode 51. N-Queens#

LeetCode 37. Sudoku Solver#

字符串问题：分割与匹配#

LeetCode 17. Letter Combinations of a Phone Number#

LeetCode 22. Generate Parentheses#

LeetCode 93. Restore IP Addresses#

LeetCode 131. Palindrome Partitioning#

LeetCode 79. Word Search#

其他经典问题#

LeetCode 494. Target Sum#

LeetCode 784. Letter Case Permutation#

剪枝技术的艺术#

1. 约束剪枝#

2. 边界剪枝#

3. 重复剪枝#

4. 可行性剪枝#

复杂度分析与优化#

常见优化技巧#

总结#

参考资料#

更多精彩内容

动态规划算法入门：从暴力递归到状态转移的完整思维指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南

单调队列算法如何在滑动窗口中保持O(n)时间复杂度