题目

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个数字的时候，当前填写完毕，回溯

代码

/**------------------------------------    *   日期：2015-02-06    *   作者：SJF0115    *   题目: 77.Combinations    *   网址：https://oj.leetcode.com/problems/combinations/    *   结果：AC    *   来源：LeetCode    *   博客：    ---------------------------------------**/    #include 
     
          #include 
      
           #include 
       
            using namespace std;    class Solution {    public:        vector
        
         
           > combine(int n, int k) {            vector
          
           
             > result; vector
            
              path; DFS(n,k,result,path,1); return result; } private: void DFS(int n,int k,vector
             
              
                > &result,vector
               
                 &path,int index){ if(path.size() == k){ result.push_back(path); return; }//if for(int i = index;i <= n;++i){ path.push_back(i); DFS(n,k,result,path,i+1); path.pop_back(); }//for } }; int main(){ Solution s; int n = 5; int k = 2; vector
                
                 
                   > result = s.combine(n,k); // 输出 for(int i = 0;i < result.size();++i){ for(int j = 0;j < k;++j){ cout<
                  
                   <<" "; }//for cout<
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

运行时间