```
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:

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