1.题目描述

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

]

2.解法分析

一种类似于深度搜索的概念，一旦找到满足的解，立马加入到结果中，用一个数组保存中间结果

class Solution {

public:

vector
           
            
              > combine(int n, int k) {
            
           

// Start typing your C/C++ solution below

// DO NOT write int main() function

vector
           
            
             > result;
            
           

if(n
           
            <=0||k<0)return result;
           

vector
           
             cur;
           

myCombine(result,cur,1,n,k);

return result;

}

void myCombine(vector
           
            
              > &result,vector
             
               &cur,int start,int n,int k)
             
            
           

{

if(k==0){result.push_back(cur);return;}

if(start>n)return;

cur.push_back(start);

myCombine(result,cur,start+1,n,k-1);

cur.pop_back();

myCombine(result,cur,start+1,n,k);

}

};