本文共 977 字，大约阅读时间需要 3 分钟。

一天一道LeetCode

本系列文章已全部上传至我的github，地址：

欢迎大家关注我的新浪微博，

欢迎转载，转载请注明出处

（一）题目

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

]

（二）解题

本题大意：给定两个整形数，ｎ和ｋ，从１～ｎ中找出所有ｋ个数的组合。

这题是典型的回溯问题。分析一下当ｎ＝４，ｋ＝3的情况：

维持一个vector变量，当它的长度小于3时，按顺序往里面放数字。

第一个满足长度等于3的组合为1，2，3，接下来回溯弹出3，继续放数字4

第二个满足长度等于3的组合为1，2，4，然后回溯弹出4，没有数字放了，就继续回溯弹出2，再放入3和4

第三个满足长度等于3的组合为1，3，4，然后回溯弹出3，4和1，放入2，3，4

第四个满足长度等于3的组合为2，3，4。至此，算法结束。

class Solution {public:    vector
   
    
     > ret;    vector
     
      
       > combine(int n, int k) {        vector
       
         temp;        dfscombine(n,1,k,temp);        return ret;    }    void dfscombine(int n,int start,int k,vector
        
          & temp) { if(temp.size()==k){ //当长度为k时，将结果存在ret中 ret.push_back(temp); return; } for(int i = start ; i <= n ; i++) { temp.push_back(i);//放入数字 dfscombine(n,i+1,k,temp); temp.pop_back();//回溯到上一步 } }};