回溯算法系统总结

最近一周写了代码随想录的回溯算法章节，总结了下回溯问题的几种问题类型和细节。

一、回溯算法概述

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会放弃该解，回到上一步，继续尝试其他可能性。

基本模板

回溯问题可以看成是一个树的问题
for循环处理同层节点，递归处理同一树枝的节点

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return; // 集合问题一般不return
    }
    
    for (选择: 本层集合中的元素) {
        处理节点;
        backtracking(路径, 选择列表);  // 递归
        回溯，撤销处理结果
    }
}

二、回溯问题分类与实现

1. 组合问题

特点：从n个元素中找出k个元素的组合，不考虑顺序，结果是叶子节点。

细节：

1. 递归索引为下一个元素，即backtracking(n, k, i + 1);
2. result添加的是新建立的ArrayList<>(path)，如果不新建，如果不new ArrayList<>,后续对path的任何修改（比如path.removeLast()）都会影响到已经存入result中的列表。适用下面的问题
3. 最后递归调用时容易把i写成startIndex

例题：77.组合

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
    
    private void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        // 剪枝优化：i <= n - (k - path.size()) + 1
        // 或者直接判断是否大于k，大于则跳过
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backtracking(n, k, i + 1);  // 注意是i+1，不是startIndex+1
            path.removeLast();
        }
    }
}

2. 分割问题

特点：在字符串的不同位置进行切割，判断当前子串是否符合要求，若符合则继续递归处理剩余部分，否则回溯。类似于组合问题。

单独写一个方法判断是否符合要求

例题：131.分割回文串

class Solution {
    List<List<String>> result = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    
    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return result;
    }
    
    private void backtracking(String s, int startIndex) {
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.add(s.substring(startIndex, i + 1));
                backtracking(s, i + 1);
                path.removeLast();
            }
        }
    }
    
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

3. 子集问题

特点：收集树的所有节点结果，而不仅仅是叶子节点。

例题：78.子集

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return result;
    }
    
    private void backtracking(int[] nums, int startIndex) {
        result.add(new ArrayList<>(path));  // 每个节点都加入结果
        
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

4. 排列问题

特点：

• 每次递归从0开始
• 需要used数组记录已使用元素

例题：46.全排列

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums, used);
        return result;
    }
    
    private void backtracking(int[] nums, boolean[] used) {
        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]);
            backtracking(nums, used);
            path.removeLast();
            used[i] = false;
        }
    }
}

5. 去重处理

一、什么情况下需要去重？

// 输入: [1,2,2]
// 不去重的结果: [[1,2], [1,2], [2,2]]  // 两个[1,2]重复
// 去重后的结果: [[1,2], [2,2]]

1. 输入数据包含重复元素

例如：

• 组合总和 II（LeetCode 40）：[1,1,2,5]，求 target=8 的组合。
  • 如果不去重，[1,2,5] 会被计算两次（因为有两个 1）。
• 全排列 II（LeetCode 47）：[1,1,2]，求所有不重复的排列。
  • 如果不去重，[1,1,2] 会因 1 的交换位置而重复出现。

2. 不同路径产生相同结果

例如：

• 子集 II（LeetCode 90）：[1,2,2]，求所有子集。
  • 如果不处理重复元素，[2] 和 [2]（来自不同的 2）会被视为两个解，但实际上它们是相同的。

---

去重三种方法：

1. 每次递归新建Set（适用于任意情况）

优点：无需排序，逻辑简单，天然实现树层去重

Set<Integer> used = new HashSet<>();
for (int i = startIndex; i < nums.length; i++) {
    if (used.contains(nums[i])) continue;
    used.add(nums[i]);
    // 其他处理
}

2. 数据少时用列表（类似Set）

List<Integer> used = new ArrayList<>();
for (int i = startIndex; i < nums.length; i++) {
    if (used.contains(nums[i])) continue;
    used.add(nums[i]);
    // 其他处理
}

3. used数组法（需要先排序）

Arrays.sort(nums);  // 必须先排序
boolean[] used = new boolean[nums.length];

for (int i = startIndex; i < nums.length; i++) {
    // 树层去重
    if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
    // 树枝去重
    // if (i > 0 && nums[i] == nums[i-1] && used[i-1]) continue;
    
    used[i] = true;
    // 其他处理
    used[i] = false;
}

6. N皇后问题

例题：51.N皇后

特点​​：

• 二维棋盘上的回溯问题
• 需要检查行、列、对角线的冲突
• 通常转化为每行放置一个皇后的形

class Solution {
    List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backtracking(n, 0, chessboard);
        return result;
    }
    
    private void backtracking(int n, int row, char[][] chessboard) {
        if (row == n) {
            result.add(arrayToList(chessboard));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') return false;
        }
        
        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') return false;
        }
        
        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') return false;
        }
        
        return true;
    }
    
    private List<String> arrayToList(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}

三、常见剪枝策略

1. 组合总和剪枝：排序后，当前和加上候选数已经超过目标值，则终止循环

for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++)

2. 排列问题剪枝：通过used数组避免重复选择

3. 子集问题剪枝：排序后，同层重复元素跳过

if (i > startIndex && nums[i] == nums[i - 1]) continue;

4. N皇后剪枝：通过isValid函数提前终止无效路径

一个问题：减枝在for循环里continue还是在for循环外return

对比：

continue：当当前元素不符合条件，但​​同层其他元素仍可能合法​​时。本质是横向剪枝（跳过同一树层的某些分支）。
break：终止当前循环，不再尝试同层的后续选项。
return：当​​整条递归路径已经不可能合法​​时。本质是纵向剪枝（提前终止整棵子树）。

剪枝方式	适用场景	代码位置	作用	例子
continue	同层剪枝、去重	for 循环内部	跳过当前选项，继续尝试下一个	组合去重、排列去重
break	后续选项必然无效	for 循环内部	终止当前循环，不再尝试后续选项	IP地址段过长时终止
return	全局剪枝、提前终止	for 循环外部（通常在递归开头）	直接终止当前递归	剩余字符无法构成合法IP时终止

四、性能优化技巧

1. 使用LinkedList而非ArrayList：频繁增删操作时性能更好
2. 提前终止条件：当发现当前路径不可能满足条件时提前返回
3. 记忆化：对于重复子问题，可以使用记忆化存储中间结果
4. 迭代替代递归：对于深度较大的问题，考虑使用迭代实现

五、常见问题与解决方案

1. 结果重复：

   • 排序后去重
   • 使用used数组标记已使用元素

2. 结果顺序错误：

   • 检查递归参数是否正确传递（特别是startIndex）
   • 检查是否在正确位置添加结果

3. 性能问题：

   • 检查是否有不必要的拷贝操作
   • 检查剪枝条件是否充分