leetcode 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],
]

1 递归一次，填入一个数字

2 填入的数字，不能是小于当前数字的值，防止重复

3 回溯：记得pop_back()最后加上的一个数字，回溯到上一层。

4 结束条件：填写够了k个数字的时候，当前填写完毕，回溯

vector
  
    > combine(int n, int k) 
	{
		vector
   
     > v; if (k > n || k==0) return v; vector
    
      mv; comb(v, mv, n, k, 1); return v; } void comb(vector
     
       > &v, vector
      
        &mv, int n, int k, int start) { for (int i = start; i <= n; i++) { mv.push_back(i); if (mv.size() == k) { v.push_back(mv); mv.pop_back(); continue; } //i
       
        
 递归的另外一种写法： 
        
 
        
 
        
void comb2(vector
         
           > &v, vector
          
            &mv, int n, int k, int start) { if (mv.size() == k) { v.push_back(mv); return; } for (int i = start; i <= n; i++) { mv.push_back(i); comb2(v, mv, n, k, i+1); mv.pop_back(); } }