14ms C++ , using bit manipulation


  • 0
    A
    class Solution {
    public:
        vector<vector<int> > combine(int n, int k) {
            vector<vector<int> > res;
    
            int comb =  (1<<k) -1;
            while (comb < 1<<n){
                vector<int> ans;
                for (int i = 0; i < n; i++){
                    if (comb>>i &1)  ans.push_back(i+1);
                }
                res.push_back(ans);
                
                //generate the next comb
                int x = comb & -comb;
                int y = comb + x;
                comb = ((comb & ~y)/x >>1) | y;
            }
            return res;
        }
    };
    

    This comes from a book. In it the way to enumerate every valid subsets is given.

    the first subset is 1 << k -1. For n = 4, and k =2, comb = 0011

    To enumerate the next the, we find the first "1"s from the right, thange the "0" left to these "1"s to be "1", and move these "1"s towords right until you remove a "1".

    Take 0101110 as an instance, and take a look about the "generate the next comb" part:

    1. x means the first "1" from the right : 00000 1 0
    2. y means thange the "0" left to these "1"s to be "1" : 01 1000 0
    3. In comb & ~y , you'll get the original "1"s, i.e. 000 111 0
    4. /x >>1 means moving these "1"s : 00000 11. Or it with y we get the next comb. i.e. 0110011

Log in to reply
 

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