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.

Example:

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

思路

一位一位叠加

例如：[1,2,3]

• 最开始是空集
• 接着处理元素1：在空集上加1，为[1]。现在有两个子集[]和[1]
• 接着处理元素2：为每个每个子集都加上元素2，得到[2]，[1, 2]。现在子集为[], [1], [2], [1, 2]
• 同理处理元素3：得到[3], [1, 3], [2, 3], [1, 2, 3]。再加上之前的子集就是所有的子集合

c++11

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res(1); //初始化一个空vector  []
        for (decltype(nums.size()) i = 0; i < nums.size(); ++i) {
            const auto size = res.size();
            for (auto j = 0; j < size; ++j) {
                res.emplace_back(res[j]);
                res.back().emplace_back(nums[i]);
            }
        }
        return res;
    }
};