算法刷题系列（三十一）：回溯算法——做选择、递归、撤销选择

算法刷题系列（三十一）：回溯算法——做选择、递归、撤销选择

排列、组合、子集和棋盘搜索看起来题型不同，背后常是同一件事：沿着一条候选路径逐步作决定；走到完整答案时记录它，走到不可能产生答案的状态时提前返回。回溯就是深度优先地枚举这些决定，并在递归返回后恢复现场。

用子集建立搜索树

给定 [2, 5, 7]，每个数字只有“选”或“不选”两种决定。递归到某个位置时，当前路径代表已经选出的子集；所有位置都处理完后，将路径的副本加入答案。

位置 0：不选 2 / 选 2
位置 1：不选 5 / 选 5
位置 2：不选 7 / 选 7

每层先复制当前路径，再尝试当前元素。递归回来后必须移除刚加入的元素，否则兄弟分支会继承不属于自己的选择。这里的状态不变量是：进入第 i 层时，路径恰好包含前 i 个位置中做出“选”决定的元素。

Java 实现

import java.util.ArrayList;
import java.util.List;

public class SubsetsBacktracking {
    public static List<List<Integer>> subsets(int[] values) {
        List<List<Integer>> answer = new ArrayList<>();
        backtrack(values, 0, new ArrayList<>(), answer);
        return answer;
    }

    private static void backtrack(
        int[] values, int index, List<Integer> path, List<List<Integer>> answer
    ) {
        if (index == values.length) {
            answer.add(new ArrayList<>(path));
            return;
        }

        backtrack(values, index + 1, path, answer);
        path.add(values[index]);
        backtrack(values, index + 1, path, answer);
        path.remove(path.size() - 1);
    }
}

Python 实现

def subsets(values: list[int]) -> list[list[int]]:
    answer: list[list[int]] = []
    path: list[int] = []

    def backtrack(index: int) -> None:
        if index == len(values):
            answer.append(path.copy())
            return

        backtrack(index + 1)
        path.append(values[index])
        backtrack(index + 1)
        path.pop()

    backtrack(0)
    return answer

assert len(subsets([2, 5, 7])) == 8
assert subsets([]) == [[]]

正确性与复杂度

每个输入位置都恰好经历“选”和“不选”两条分支，因此每个子集恰好对应一条从根到叶的路径；叶节点收集所有路径，故答案既不遗漏也不重复。n 个元素产生 2^n 个子集，复制结果还需要 O(n)，时间为 O(n·2^n)，递归路径空间为 O(n)（不计输出）。

边界与易错点

• 空输入只有一个子集：空集 [[]]，不是没有子集。
• 必须把路径复制进答案；若直接保存同一个可变列表，回溯清空路径后结果也会变空。
• pop/remove 必须与本层的 append 配对，且只撤销本层做出的选择。
• 若输入含重复值，上述按“位置”枚举会产生内容相同的子集。要求唯一子集时，先排序，并在同一层跳过相同值；不要把“不同位置”误当成“不同数值答案”。
• 这份实现枚举所有子集，没有目标约束可供剪枝。遇到组合和排列题时，应先写出状态、选择范围和终止条件，再判断哪些分支不可能成功。

回溯的三个动作缺一不可：做选择建立新状态，递归探索后续，撤销选择恢复父状态。把这个状态不变量写清楚，通常比一上来套模板更能避免漏解和重复。