Simple C++ Solution


  • 1
    A

    Let's start with a simple example.
    Example 1:
    We have to find all the subsets of set {1}. The possible answers are {} and {1}. Here is how we can reach this solution:-
    We start with an empty set {}. Then we add {1} to it and take its union with the empty set. After we add {1} to it, it becomes {1} and its union with the empty set becomes {{}, {1}}

    Example 2:
    We start with empty set {}. Then we add {1} to it and take its union with the empty set.
    After we add {1} to it, it becomes {1} and its union with the empty set becomes {{}, {1}}.
    Now, we add {2} to the above set and it becomes {{2}, {1, 2}} and then we take its union with {{},{1}} and so it becomes {{},{1},{2}, {1, 2}}.

    Here is the code with more explanation

    vector<vector<int>> subsets(vector<int>& nums) {
            //adding empty set to the answer
            vector<vector<int> > result(1, vector<int>()); 
            
            //Iterating one by one through the set of which we need to find the subsets of
            for(int i = 0; i < nums.size(); i++) {
                int n = result.size(); //Taking the original size of the subset
                for(int j = 0; j < n; j++) { 
                    result.push_back(result[j]); //Now adding those elements back again 
                    result.back().push_back(nums[i]); //Now taking the last element and adding the new element to it
                }
            }
            
            return result;
        }
    

    Here is how the above code works:
    First we create a vector of vectors result.
    Then we add an empty set {} to it.
    Then inside the inner loop, we replicate the inner set so it becomes {{},{}}
    Now we take the last element and add {1} to it. So, no it becomes {{},{1}}

    In the next iteration of the outer loop:
    We enter the inner loop. Now {{},{1}} becomes {{},{1},{}}
    Then we add the {2} to it at the end. So it becomes {},{1},{2}}.
    The loop continues and we add {1} at the end so now it becomes {{},{1},{2},{1}
    Now we take the last element and add {2} to it so now it becomes {{},{1},{2},{1,2}}


  • 0
    I

    I am attaching my solution. I used a standard code for selecting combinations in C++ using std::next_permutation

    #include <algorithm>
    
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            
            vector<vector<int>> subsets;
            
            for (size_t n = 0; n <= nums.size(); ++n) {
                vector<bool> sels(nums.size());
                std::fill(sels.begin(), sels.end()-n, false);
                std::fill(sels.end()-n, sels.end(), true);
                
                
                do {
                    vector<int> subset;
                    for(size_t i = 0 ; i < nums.size(); ++i) {
                        if(sels[i])
                            subset.push_back(nums[i]);
                    }
                    subsets.push_back(subset);
                } while(std::next_permutation(sels.begin(), sels.end()));
                
                vector<int> nums_perm =  nums;            
            }
            
            return subsets;         
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.