C++ Recursive/Iterative/Bit-Manipulation Solutions with Explanations


  • 151

    Recursive (Backtracking)

    This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> subs;
            vector<int> sub;  
            genSubsets(nums, 0, sub, subs);
            return subs; 
        }
        void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& subs) {
            subs.push_back(sub);
            for (int i = start; i < nums.size(); i++) {
                sub.push_back(nums[i]);
                genSubsets(nums, i + 1, sub, subs);
                sub.pop_back();
            }
        }
    };
    

    Iterative

    This problem can also be solved iteratively. Take [1, 2, 3] in the problem statement as an example. The process of generating all the subsets is like:

    1. Initially: [[]]
    2. Adding the first number to all the existed subsets: [[], [1]];
    3. Adding the second number to all the existed subsets: [[], [1], [2], [1, 2]];
    4. Adding the third number to all the existed subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

    Have you got the idea :-)

    The code is as follows.

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> subs(1, vector<int>());
            for (int i = 0; i < nums.size(); i++) {
                int n = subs.size();
                for (int j = 0; j < n; j++) {
                    subs.push_back(subs[j]); 
                    subs.back().push_back(nums[i]);
                }
            }
            return subs;
        }
    }; 
    

    Bit Manipulation

    This is the most clever solution that I have seen. The idea is that to give all the possible subsets, we just need to exhaust all the possible combinations of the numbers. And each number has only two possibilities: either in or not in a subset. And this can be represented using a bit.

    There is also another a way to visualize this idea. That is, if we use the above example, 1 appears once in every two consecutive subsets, 2 appears twice in every four consecutive subsets, and 3 appears four times in every eight subsets, shown in the following (initially the 8 subsets are all empty):

    [], [], [], [], [], [], [], []

    [], [1], [], [1], [], [1], [], [1]

    [], [1], [2], [1, 2], [], [1], [2], [1, 2]

    [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

    The code is as follows.

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int num_subset = pow(2, nums.size()); 
            vector<vector<int> > res(num_subset, vector<int>());
            for (int i = 0; i < nums.size(); i++)
                for (int j = 0; j < num_subset; j++)
                    if ((j >> i) & 1)
                        res[j].push_back(nums[i]);
            return res;  
        }
    };
    

    Well, just a final remark. For Python programmers, this may be an easy task in practice since the itertools package has a function combinations for it :-)


  • 6

    Interesting way to use the bit masks, building all subsets in parallel. I don't think I've seen that before. Made me write a way to "only iterate over the 1-bits":

        for (int i = 0; i < nums.size(); i++)
            for (int step = 1 << i, start = 0; start < num_subset; start += 2 * step)
                for (int j = start; j < start + step; j++)
                    res[j].push_back(nums[i]);
    

    Don't know whether it's faster. Overall, half of the bits are 1 anyway, so I save at most 50%. And I might have more overhead costs.

    Python's combinations doesn't quite do it, btw, it only creates subsets of a certain size. But it can be used, yes. Doesn't help much compared to other solutions, though, as you can see here. And Ruby is even shorter :-)


  • 0

    Hi, Stefan. Your code is much more concise. BTW, Ruby is really nom nom nom :-)


  • 1
    D

    Both two bitmap solutions are cool, but what if the input vector size is much much bigger than 32?


  • 0

    It can't be much bigger, and the OJ doesn't even get close to 32. The output contains 2n subsets, which takes a lot of memory and computation time. If you had a very big computer and more time than the OJ gives us, then the input could be a bit bigger. But then we could just use 64-bit ints, that would suffice.


  • 0
    Q

    yet another backtracking way.

    class Solution {
        vector<vector<int>> res;
        void addSubset(std::vector<int> &inset,std::vector<int> &rest) {
            if(rest.empty()) res.push_back(inset);
            else {
                auto x=rest.back(); rest.pop_back();
                addSubset(inset,rest);
                
                inset.push_back(x);
                addSubset(inset,rest);
                
                inset.pop_back();
                rest.push_back(x);
            }
        }
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            res.clear();
            std::sort(nums.begin(),nums.end(),[](const int x,const int y) { return x>y; });
            std::vector<int> inset, &rest=nums;
            addSubset(inset,rest);
            return res;
        }
    };

  • 0
    M

    I know the time complexity is 2 power n of the recursive because we have those many subsets, but how do i get there with a mathematical formula? anyone please?, i was asked this in a startup interview today! I tried with masters theorem but couldn't get there


  • 0
    S

    In this case i think T(n) = T(n-1) + T(n-2) + ... + T(1) = (T(n-2) + T(n-1) + ...) + T(n-2) + T(n - 1) + … = 2T(n-2), so on and so forth, T(n) = 2T(n-1) = 4T(n-2) = … = 2^nT(1), where I think T(1) is O(1).


  • 0
    Y

    for bit manipulation, could use bitmap to further reduce the memory if the nums.size() is huge.


  • 0

    @jianchao.li.fighter Hi Janchao! Can I ask why you sort the nums? I am not really understand.:confused:


  • 0

  • 0

    @StefanPochmann Is this question different for different type of users? In my question, there is no this note "Elements in a subset must be in non-descending order".


  • 0

    @wtsanshou If you look at the top of the web archive page I showed you, you'll see that that's what the page looked like on April 5. Meaning the problem was simply modified recently, and well after @jianchao-li-fighter had posted these solutions.


  • 0

    @StefanPochmann Thank you Stefan! I got it.


  • 0
    F
    This post is deleted!

  • -1
    This post is deleted!

  • 0

    said in C++ Recursive/Iterative/Bit-Manipulation Solutions with Explanations:

    sub.pop_back();

    why do you have to sub.pop_back();?


Log in to reply
 

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