Leetcode dfs Combinations

Combinations

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; }