LeetCode 78. 子集

◎

本节目标

在每个搜索节点收集当前路径，用 start 保证每个子集只生成一次。

这道题继续使用回溯决策树，但答案不只存在于叶子：任意已选路径本身就是一个合法子集。

查看 LeetCode 原题

题意与约束

给定一组互不相同的整数，返回所有子集，空集也必须包含。子集不关心元素排列顺序，因此 [1, 2] 和 [2, 1] 是同一个结果。

朴素思路与瓶颈

位掩码可以枚举每个元素选或不选的状态，但不容易直接迁移到长度受限或带剪枝的组合问题。回溯把一个节点解释为“已经选出的集合”，并自然保留可继续扩展的选择范围。

节点即答案

进入 backtrack(start) 时，当前 path 已经由严格递增的下标构成，因此立刻复制到答案。接着从 start 枚举下一个下标，并把下一层起点设为 index + 1。这保证每个元素最多出现一次，也保证同一集合不会因为选择顺序不同重复生成。

根节点的空路径就是空集；越深的节点表示元素更多的子集。与全排列相比，这里不需要 used，因为 start 已经排除了返回前面下标的可能。

代码实现

C++

C++17

#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> answer;
    vector<int> path;

    void backtrack(const vector<int>& nums, int start) {
        answer.push_back(path);
        for (int index = start; index < static_cast<int>(nums.size()); index++) {
            path.push_back(nums[index]);
            backtrack(nums, index + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        answer.clear();
        path.clear();
        backtrack(nums, 0);
        return answer;
    }
};

Python

Python 3

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        answer: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            answer.append(path.copy())
            for index in range(start, len(nums)):
                path.append(nums[index])
                backtrack(index + 1)
                path.pop()

        backtrack(0)
        return answer

复杂度分析

共有 2^n 个子集。若把复制出的元素数量计入，全部答案总长度为 n · 2^(n - 1)，时间复杂度为 O(n · 2^n)。递归栈和当前路径额外占用 O(n) 空间，答案占用 O(n · 2^n) 空间。

易错点

• 只在没有可选元素时收集，漏掉空集和所有非叶子子集。
• 下一层仍传 start，使同一个元素被重复选择。
• 从零重新枚举所有元素，产生同一子集的多个排列版本。

模式迁移

组合、选取固定数量元素和枚举递增序列都可先从子集模板出发。若每个选择还必须满足目标和、回文或几何约束，则在递归前加入相应合法性判断和剪枝。