Problem 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],
    []
  ]
  

• 解题思路
  假设输入的数组为 nums，且 nums 的大小为 n。则要找出 nums 的所有子集，我们就要分别找出 nums 中长度为0（空集）、1、2……n的子集，将这些子集存储在 res 中，即可得到 nums 的所有子集。

  假设 nums 中的元素为 nums[0]、nums[1]、……nums[n-1]，若要找出 nums 中长度为 len 的子集，其中len <= n，可以先将 nums[0] 加入到子集 sub 中，再从 nums[1] 到 nums[n-1] 中选择 len-1 个加入到 sub；随后将 nums[1] 加入到子集 sub 中，再从 nums[2] 到 nums[n-1] 中选择 len-1 个加入到 sub 中……以此类推，就能将所有长度为 len 的子集 sub 存储到 res 中。

  下面给出了用递归实现上述算法的代码：

• 代码实现

class Solution {
public:
    vector<vector<int> > subsets(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> sub;
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= nums.size(); ++i){
            helper(res, sub, nums, 0, i);
        }
        return res;
    }
    void helper(vector<vector<int> >& res, vector<int> &sub, vector<int> &nums, int star, int len){
        if(len == 0){
            res.push_back(sub);
            return ;
        }
        for(int i = star; i < nums.size(); ++i){
            sub.push_back(nums[i]);
            helper(res, sub, nums, i+1, len-1);
            sub.pop_back();
        }
    }
};

---