回溯的核心思想是：在尝试一条路径后，恢复到之前的状态，以便尝试其他路径。

需要"减去"的情况

当你在递归调用之前修改了状态，那么在递归调用之后就需要"减去"（恢复状态）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 情况1：使用全局/成员变量
private int sum = 0;

public void backtrack(int[] candidates, int target, int index) {
    if (sum == target) {
        // 找到解
        return;
    }
    
    for (int i = index; i < candidates.length; i++) {
        // 修改状态
        sum += candidates[i];           // 加上
        route.add(candidates[i]);
        
        // 递归
        backtrack(candidates, target, i);
        
        // 恢复状态（需要减去）
        sum -= candidates[i];           // 减去
        route.remove(route.size() - 1);
    }
}

不需要"减去"的情况

当状态通过参数传递时，不需要显式"减去"，因为每次递归调用都有自己独立的状态副本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 情况2：通过参数传递状态
public void backtrack(int[] candidates, int target, int currentSum, int index) {
    if (currentSum == target) {
        // 找到解
        return;
    }
    
    for (int i = index; i < candidates.length; i++) {
        // 递归时传递新的状态，不修改当前状态
        backtrack(candidates, target, currentSum + candidates[i], i); // 不需要恢复
        // 注意：route仍然需要回溯，因为它是可变对象
        route.add(candidates[i]);
        backtrack(candidates, target, currentSum + candidates[i], i);
        route.remove(route.size() - 1); // route需要显式回溯
    }
}

关键区别

  1. 成员变量 vs 参数传递：
    • 成员变量：需要显式恢复状态（加减操作）
    • 参数传递：自动"恢复"，因为递归返回后参数值不变
  2. 可变对象 vs 基本类型：
    • 可变对象（如List）：总是需要显式回溯
    • 基本类型（如int）：如果是参数传递，不需要显式回溯