# 78. 子集

# 题目描述

给定一个整数数组 nums，数组中的元素互不相同，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，可以按任意顺序返回。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

1
2

示例 2：

输入：nums = [0]
输出：[[],[0]]

1
2

# 思路

子集问题和组合问题有什么不同？

如果都抽象成一棵树，组合问题通常收集指定深度的叶子节点，而子集问题要收集树上的所有节点。空集就是根节点，选择一个元素、两个元素直到全部元素，都是合法答案。

子集是无序的，[1,2] 和 [2,1] 是同一个子集，所以仍然需要 startIndex：取过的元素不能回头再取。

回溯三部曲：

参数用 startIndex 表示下一次选择的起点。
进入每个递归节点时立刻收集 path；显式终止条件可以不写。
从 startIndex 开始选择，递归传入 i + 1，返回后撤销选择。

本题不需要剪枝，因为每一个节点都是答案，整棵树都要遍历。

# 模拟过程

以 nums = [1,2,3] 为例：根节点先收集 []；选择 1 后收集 [1]；继续选择 2、3，依次收集 [1,2]、[1,2,3]。回溯后再搜索 [1,3]，随后从根节点搜索以 2、3 开头的分支。

# 解题代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 树上的每个节点都是一个子集
        for (int i = startIndex; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear(); path.clear();
        backtracking(nums, 0);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 复杂度分析

时间复杂度：O(n × 2^n)，共 2^n 个子集，复制每个子集最多需要 O(n)。
空间复杂度：O(n)，不计返回结果，递归栈和路径最大深度为 n。

# 其他语言

# Python3

class Solution:
    def subsets(self, nums):
        result, path = [], []
        def backtracking(start):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i]); backtracking(i + 1); path.pop()
        backtracking(0)
        return result

1
2
3
4
5
6
7
8
9

# Java

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) { backtracking(nums, 0); return result; }
    void backtracking(int[] nums, int start) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]); backtracking(nums, i + 1); path.removeLast();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11

# Go

func subsets(nums []int) [][]int {
    result, path := [][]int{}, []int{}
    var dfs func(int)
    dfs = func(start int) {
        result = append(result, append([]int{}, path...))
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i]); dfs(i+1); path = path[:len(path)-1]
        }
    }
    dfs(0); return result
}