Programming Skills: Subsets

[Problem]
https://leetcode.com/problems/subsets/description/

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

中文翻譯:
給你一個集合，集合內的數字都不相同
請回傳所有的子集合

[Solution]

Dynamic programming.
The answer of K numbers is based on answer of K-1 numbers.

Let's assume the input is [1,2], so the power set are:
[]
[1]
[2]
[1,2]

Now we extend the input by putting one more number into it [1,2,3].
For every existing subset, we can decide we want to add the new number '3' into it or not.
In the DON'T ADD case, all subsets are:
[]
[1]
[2]
[1,2]
In the ADD case, all subsets are:
[3]
[1,3]
[2,3]
[1,2,3]

The power set of [1,2,3], is the union of DON'T ADD case and ADD case.

So the conclusion is :
The power set of K numbers is the union of
DON'T ADD K to K-1's power set, and ADD K to K-1's power set.

Let's write code~


class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        ans.push_back(vector<int>(0)); //add base case
        for(int i=0;i<nums.size();i++){
            //add nums[i] into all previous sets
            int pre_set_num = ans.size();
            for(int s=0;s<pre_set_num;s++){
                vector<int> newset = ans[s];
                newset.push_back(nums[i]);
                ans.push_back(newset);
            }
        }
        return ans;
    }    
};

[Method 2]
And here is another recursive method which is easy to understand.
For each element in the input array, we can decide we wanna keep it or not.
By recursively doing this, we can find all combination.


class Solution {
public:

    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> subset(0);
        DFS(nums, subset, ans, 0);
        return ans;
    }
    
    void DFS(vector<int>& nums, vector<int>& subset,vector<vector<int>>& ans, int target){
        if(target == nums.size()){
            ans.push_back(subset);
            return;
        }
    
        DFS(nums, subset, ans, target+1);
        subset.push_back(nums[target]);
        DFS(nums, subset, ans, target+1);
        subset.pop_back();
        return;        
    }
};