problem：
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],
]
Hide Tags
Backtracking
题意：输出1~n的 k 个数字的所有排列组合
thinking：
（1）看到题就应想到用DFS深搜法
（2）深搜的难点在于下1步怎样处理，这里开1个K大小的数组，记录深搜的每步获得的数字
（3）时间复杂度为O（K*N），空间复杂度为O（k）
code：
class Solution {
private:
vector<vector<int> > ret;
vector<int> tmp;
public:
vector<vector<int> > combine(int n, int k) {
ret.clear();
tmp.resize(k);
dfs(1,n,k,1);
return ret;
}
protected:
void dfs(int dep, int n, int k,int start)
{
if(dep>k)
{
ret.push_back(tmp);
return;
}
for(int i=start;i<=n;i++)
{
tmp[dep⑴]=i;
dfs(dep+1,n,k,i+1);
}
}
};