子集

GitHub跳转原题关系图返回列表

每个元素选/不选的 DFS，或枚举二进制 mask。

OJ: leetcodecn

题目 ID: subsets

难度:普及+/提高

标签:回溯DFS位运算cpppython

日期: 2026-07-29 13:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

返回数组所有子集。

思路

DFS 选/不选分支，到叶子时收集结果。也可用枚举 mask。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> ans;
        vector<int> cur;
        function<void(int)> dfs = [&](int i) {
            if (i == (int)nums.size()) {
                ans.push_back(cur);
                return;
            }
            dfs(i + 1);
            cur.push_back(nums[i]);
            dfs(i + 1);
            cur.pop_back();
        };
        dfs(0);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (auto &v : Solution().subsets(a)) {
        for (int x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans, cur = [], []

        def dfs(i):
            if i == len(nums):
                ans.append(cur[:])
                return
            dfs(i + 1)
            cur.append(nums[i])
            dfs(i + 1)
            cur.pop()

        dfs(0)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    for v in Solution().subsets(a):
        print(*v)


if __name__ == "__main__":
    main()

复杂度

时间 O(n·2^n)。

总结

选/不选 DFS 是子集枚举的标准递归写法。