LeetCode 78. 子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

题解

由于数组中不含重复元素，每个元素有两种可能，放入子集或不放入子集，所以子集共有 2ⁿ 个。

递归（回溯法）

代码

// C++
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ret;
    vector<int> subnums;
    recursiveVisit(ret, 0, subnums, nums);
    return ret;
}
void recursiveVisit(vector<vector<int>>& ret, int level, vector<int>& subnums, vector<int>& nums) {
    ret.push_back(subnums);
    for (auto i = level; i < nums.size(); ++i) {
        subnums.push_back(nums[i]);
        recursiveVisit(ret, i + 1, subnums, nums);
        subnums.pop_back();
    }
}

迭代法

算法

• 对所有元素迭代，将每个元素放入之前已有的子集。
• 以 [1,2,3] 为例：
  1. 初始子集： [[]]
  2. 将第一个元素放入所有子集：[[],[1]]
  3. 将第二个元素放入所有子集：[[],[1],[2],[1,2]]
  4. 将第三个元素放入所有子集：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

代码

// C++
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ret = {{}};
    for (auto i = 0; i < nums.size(); ++i) {
        int retSize = (int)ret.size();
        for (auto j = 0; j < retSize; ++j) {
            auto subnums = ret[j];
            subnums.push_back(nums[i]);
            ret.push_back(subnums);
        }
    }
    return ret;
}

参考链接

• C++ Recursive/Iterative/Bit-Manipulation, LeetCode discuss.

类似题目

• 子集 II