Bit manipulation C++ solution with explanation


  • 0
    M

    Each Subset can be composed as bit multiplication i * nums[] where i: 0..pow(2,n)-1.
    If binary representation of i contains 1 on appropriate place, this element of given set goes to the current subset.
    For example, if our set is [1,2,3], i: [0, 8]. When i=5 it will be 101 in binaries representation and result subset is 101*[1,2,3] = [1,3] so on.

    class Solution {
    public:
        vector < vector <int> > res;
        void form(uint i, vector<int>& nums){
            vector <int> a;
            res.push_back(a);
            for (uint j = 0; j < nums.size(); j++){
                if (i & 1) { // equal to 1 when significant bit is 1
                    res[res.size()-1].push_back(nums[j]);
                }
                i = (i >> 1); //right shift moves sighnificant bit to the rightest position
            }
        }
        vector<vector<int>> subsets(vector<int>& nums) {
            int maxx = pow(2,nums.size());
            for (uint i = 0; i < maxx; i++){    //travers all numbers till pow(2,n)-1
                form(i, nums);
            }
            return res;
        }
    };
    

Log in to reply
 

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