vvrf / DSA.log

问题拆解

给一个互不相同的整数数组，返回它所有的子集（幂集）。

子集和排列、组合最大的不同是：它不限定选多少个，空集和全集都算。想靠嵌套循环枚举“选一个的”“选两个的”……层数不定，写不出来。换个视角：一个子集完全由“每个元素在不在里面”决定，n 个元素各自独立地回答“在 / 不在”，所以总共恰好 2^n 个子集。

这个视角直接给出了递归结构：按下标从左到右处理，每个位置分两个分支——把当前元素放进路径，或者跳过它。走到数组末尾时，路径就是一个完整的子集。

子集问题没有“合法性”要剪枝，回溯树上每个节点都通向答案；难的不是搜索，是想清楚一条根到叶的路径为什么恰好对应一个子集。

按 start 枚举的回溯

实践中更常用的写法是“按 start 枚举”：每层从 start 开始枚举下一个进入子集的元素，并且进入递归前就把当前路径记入答案。这样答案是在树的每个节点收集的（而不只是叶子），天然避免重复——因为元素只往后选，[1, 2] 和 [2, 1] 不会都出现。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path)); // 每个节点都是一个子集，进来先收集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res); // 只往后选，避免重复
        path.remove(path.size() - 1);      // 撤销选择
    }
}

def subsets(nums: List[int]) -> List[List[int]]:
    res = []
    path = []

    def backtrack(start: int) -> None:
        res.append(path[:])  # 每个节点都是一个子集，进来先收集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)  # 只往后选，避免重复
            path.pop()        # 撤销选择

    backtrack(0)
    return res

func subsets(nums []int) [][]int {
    res := [][]int{}
    path := []int{}
    var backtrack func(start int)
    backtrack = func(start int) {
        res = append(res, slices.Clone(path)) // 每个节点都是一个子集，进来先收集
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i + 1) // 只往后选，避免重复
            path = path[:len(path)-1] // 撤销选择
        }
    }
    backtrack(0)
    return res
}

pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    fn backtrack(nums: &[i32], start: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        res.push(path.clone()); // 每个节点都是一个子集，进来先收集
        for i in start..nums.len() {
            path.push(nums[i]);
            backtrack(nums, i + 1, path, res); // 只往后选，避免重复
            path.pop(); // 撤销选择
        }
    }
    let mut res = Vec::new();
    backtrack(&nums, 0, &mut Vec::new(), &mut res);
    return res;
}

两个易错点：收集答案时必须拷贝一份路径（new ArrayList<>(path)、path[:]、slices.Clone），否则 res 里存的全是同一个还在被修改的引用，最后每个“子集”都变成空的；Go 里如果直接 append(res, path)，后续对底层数组的写入还可能污染已收集的结果，拷贝同样不可省。

二进制位枚举

2^n 个子集正好对应 0 到 2^n - 1 这些整数：第 j 位是 1 就表示 nums[j] 入选。一层循环扫掩码、一层循环查位，不用递归也能生成全部子集。

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> cur = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((mask >> j & 1) == 1) { // 第 j 位为 1 则选 nums[j]
                cur.add(nums[j]);
            }
        }
        res.add(cur);
    }
    return res;
}

def subsets(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res = []
    for mask in range(1 << n):
        # 第 j 位为 1 则选 nums[j]
        res.append([nums[j] for j in range(n) if mask >> j & 1])
    return res

func subsets(nums []int) [][]int {
    n := len(nums)
    res := make([][]int, 0, 1<<n)
    for mask := 0; mask < 1<<n; mask++ {
        cur := []int{}
        for j := 0; j < n; j++ {
            if mask>>j&1 == 1 { // 第 j 位为 1 则选 nums[j]
                cur = append(cur, nums[j])
            }
        }
        res = append(res, cur)
    }
    return res
}

pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut res = Vec::with_capacity(1 << n);
    for mask in 0..(1u32 << n) {
        // 第 j 位为 1 则选 nums[j]
        let cur: Vec<i32> = (0..n).filter(|&j| mask >> j & 1 == 1).map(|j| nums[j]).collect();
        res.push(cur);
    }
    return res;
}

位枚举胜在没有递归、代码短，且天然给每个子集一个编号；缺点是 n 稍大（超过 31/63）就受整数位宽限制，而且不像回溯那样容易加剪枝，适合 n ≤ 20 的纯枚举场景。

复杂度

指标	复杂度	原因
时间	`O(n × 2^n)`	2^n 个子集，收集每个平均花 O(n) 拷贝
空间	`O(n)`	递归深度或位检查的临时开销，不计答案本身

可以迁移的模式

“每个元素独立二选一”的问题，解空间就是 2^n，回溯与位枚举是同一棵树的两种走法；
组合类回溯用 start 参数保证“只往后选”，是消除顺序重复的通用手段；
收集路径时务必深拷贝，共享可变引用是回溯题最高频的 bug。

后续的子集 II（含重复元素）只是在这套骨架上多加一行“同层去重”的判断。