78. 子集

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解法

方法一：DFS(回溯)

思考

每个元素只有选与不选两种可能，子集共 \(2^n\) 个。\(n \le 10\)，全部列出即可。

递归可以按元素下标展开这棵决策树：从下标 \(i\) 出发，先不选 \(nums[i]\)，再选中并回溯弹出。当 \(i = n\) 时将当前路径拷入答案。题目保证元素互不相同，因此不会产生重复子集。

我们设计一个函数 \(dfs(i)\)，表示从数组的第 \(i\) 个元素开始搜索所有子集。函数 \(dfs(i)\) 的执行逻辑如下：

如果 \(i=n\)，表示当前已经搜索结束，将当前得到的子集 \(t\) 加入答案数组 \(ans\) 中，然后返回；
否则，我们可以选择不选择当前元素，直接执行 \(dfs(i+1)\)；也可以选择当前元素，即把当前元素 \(nums[i]\) 加入子集 \(t\)，然后执行 \(dfs(i+1)\)，注意要在执行 \(dfs(i+1)\) 以后再将 \(nums[i]\) 从子集 \(t\) 中移除（回溯）。

在主函数中，我们调用 \(dfs(0)\)，即从数组的第一个元素开始搜索所有子集。最后返回答案数组 \(ans\) 即可。

时间复杂度 \(O(n\times 2^n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组的长度。一共有 \(2^n\) 个子集，每个子集需要 \(O(n)\) 的时间来构造。

Python3JavaC++GoTypeScriptRust

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == len(nums):
                ans.append(t[:])
                return
            dfs(i + 1)
            t.append(nums[i])
            dfs(i + 1)
            t.pop()

        ans = []
        t = []
        dfs(0)
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        dfs(i + 1);
        t.add(nums[i]);
        dfs(i + 1);
        t.remove(t.size() - 1);
    }
}

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

func subsets(nums []int) (ans [][]int) {
    t := []int{}
    var dfs func(int)
    dfs = func(i int) {
        if i == len(nums) {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        dfs(i + 1)
        t = append(t, nums[i])
        dfs(i + 1)
        t = t[:len(t)-1]
    }
    dfs(0)
    return
}

function subsets(nums: number[]): number[][] {
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number) => {
        if (i === nums.length) {
            ans.push(t.slice());
            return;
        }
        dfs(i + 1);
        t.push(nums[i]);
        dfs(i + 1);
        t.pop();
    };
    dfs(0);
    return ans;
}

impl Solution {
    fn dfs(i: usize, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
        if i == nums.len() {
            ans.push(t.clone());
            return;
        }
        Self::dfs(i + 1, t, ans, nums);
        t.push(nums[i]);
        Self::dfs(i + 1, t, ans, nums);
        t.pop();
    }

    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut ans = Vec::new();
        Self::dfs(0, &mut Vec::new(), &mut ans, &nums);
        ans
    }
}

方法二：二进制枚举

思考

方法一依靠递归栈把「选 / 不选」展开，调用开销与递归深度均为 \(O(n)\)。

\(n\) 很小，也可以把每个子集对应成 \([0, 2^n)\) 中的一个掩码：第 \(i\) 位为 \(1\) 则收入 \(nums[i]\)。少一层函数调用，时间复杂度同为 \(O(n \times 2^n)\)。

我们也可以使用二进制枚举的方法得到所有的子集。

我们可以使用 \(2^n\) 个二进制数来表示 \(n\) 个元素的所有子集，对于当前二进制数 \(mask\)，如果第 \(i\) 位为 \(1\)，表示选择了第 \(i\) 个元素，否则表示不选择第 \(i\) 个元素。