LeetCodeDay53 —— 子集★★

78. 子集 Subsets

描述

• Given a set of distinct integers, nums, return all possible subsets (the power set).
• Note: The solution set must not contain duplicate subsets.

示例

Input:
 nums = [1,2,3]
Output:
  [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
  ]

思路

1. 子集就是包含集合中的某些数，对于一个数而言只存在有这个数和没这个数两种状态。所以可以遍历集合中的每个数，依次递归考虑每个数包含和不包含的情况。思路比较暴力。
2. 包含第 i 个元素的所有子集，其实就是在 subsets[i-1] 的每个子集上添加上一个 a[i]。subsets 初始为空，依次遍历每个元素，将 subsets 中的每个子集 copy 出来加上 a[i]，然后添加到 subsets 中去。
   (参考)

// 递归，类似全排列。考虑每个数包含于不包含的情况
class Solution_78_01 {
 public:
  vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<int> num;
    vector<vector<int>>& ret;
    _subsets(0, nums.size(), num, nums, ret);
    return ret;
  }
  void _subsets(int k, int size, vector<int>& num, vector<int>& nums,
                vector<vector<int>>& ret) {
    if (k == size) {
      ret.push_back(num);
      return;
    }
    num.push_back(nums[k]);
    _subsets(k + 1, size, num, nums, ret);
    num.pop_back();
    _subsets(k + 1, size, num, nums, ret);
  }
};

// 非递归, subsets[i] = subsets[i - 1] + ((Each Subset in subsets[i-1]) + a[i]))
class Solution_78_02 {
 public:
  vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> ret;
    vector<int> tmp;
    ret.push_back(tmp);
    for (int num : nums) {
      int size = ret.size();
      for (int i = 0; i < size; ++i) {
        tmp = ret[i];
        tmp.push_back(num);
        ret.push_back(tmp);
      }
    }
    return ret;
  }
};