Combinations
Total Accepted: 18327 Total Submissions: 60479My Submissions
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],
]
题意：给定两个数字 n 和 k，给出从1...n数字中取 k个的所有可能组合
思路：dfs
递归的深度为 k，第 i 层的第j个节点有 n - i - j 个选择分支
复杂度：时间 O(n^k)，空间O(k)
vector
> res;
int nn, kk;
void dfs(int cur, int start, vector
&path){ if(cur == kk ){ res.push_back(path); } for(int i = start; i <= nn; i++){ path.push_back(i); dfs(cur + 1, i + 1, path); path.pop_back(); } } vector
> combine(int n, int k){ nn = n, kk = k; vector
path; dfs(0, 1, path); return res; }