Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
分析：
DFS + 剪枝。
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<int> path;
vector<vector<int> > res;
DFS(1, n, k, path, res);
return res;
}
private:
void DFS(int cur, int n, int k, vector<int>&path, vector<vector<int> >&res)
{
// exit
if(k == 0){
res.push_back(path);
return;
}
//only k elems left
else if(n-cur+1 == k){
for(int i=cur; i<=n; ++i)
path.push_back(i);
res.push_back(path);
path.erase(path.end()-k, path.end());
return;
}
//pick cur
path.push_back(cur);
DFS(cur+1, n, k-1, path, res);
path.pop_back();
// do not pick cur
DFS(cur+1, n, k, path, res);
}
};