Leetcode #78 Subse

This is a problem that finding all possible subsets (power set) from givien integer array.

 

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

 

Each element of the array can be add to subset or not which is 2 number of cases each.

Therefore total number of cases that can be made with 3 elements of array is 8 (2^3).

 

First level branches indicates that either adding 1 or not to the subset.

Second level branches indicates that either adding 2 or not to the subset. 

Third level branches indicates that either adding 3 or not to the subset.

 

As you can see there are recursive pattern that either adding or not of each level of branches.

 

class Solution {
public:
    
    void search(int index, vector<int>& nums, vector<int>& subset, vector<vector<int>>& uniqueSet) {
        if(index == nums.size()){
       		
            //index hits the size of array so break recurstion and add the unique subsets.
            uniqueSet.push_back(subset);
            return;
        }
        else{
        	
            // Adding nums[index] to subset
            subset.push_back(nums[index]);
            search(index + 1, nums, subset, uniqueSet);
			
            // Not adding nums[index] to subset
            // By poping what we just added on the top. 
            subset.pop_back();
            search(index + 1, nums, subset, uniqueSet);
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {

        vector<vector<int>> uniqueSet;
        vector<int> subset;
        search(0, nums, subset, uniqueSet);
        return uniqueSet;
    }
};