Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
給你數字1~n，說要從中挑k個出來。排列順序沒差，也就是求組合而已。
[Solution]
1.
"Combination" means :
If I have a sequence of numbers, then all permutations of this sequence are the same to me.
Which means if I have sequence [2,5,9], 259,295,529,592,925,952 are the same to me.
So we come up with an idea :
We can use the first permutation(who is ascending) to represent all the other permutations.
e.g.
I have a sequence [2,5,9] and there are 6 permutations of this sequence
which are 259,...,952. I just use "259" to represent the others.
2.
We are asked to pick K numbers from the sequence [1,2,..,n].
We apply the above idea when picking numbers to avoid duplicated combination.
That is : We only choose the one who is larger than the previous chosen one.
e.g.
In [1,2,3,4,5], after choosing '2', I can only choose '3' or '4' or '5'.
Now let's implement this idea.
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> comb;
picknum(1,n,k,comb,res);
return res;
}
void picknum(int start, //start number of the sequence
int end, //end number of the sequence
int k, //how many number you wanna pick
vector<int>& comb, //current picked number
vector<vector<int>>& res){
if(end-start+1 < k)
return;
if(k==0){
res.push_back(comb);
return;
}
for(int i=start;i<=end;i++){
comb.push_back(i);
picknum(i+1,end,k-1,comb,res);
comb.pop_back();
}
}
};
