题目描述

 

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2输出:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

 

解题思路

 

回溯法，每次遍历到一个元素分为放入与不放入集合两种情况，若集合长度为k，则加入到结果中。

 

代码

 

1 class Solution { 2 public: 3     vector
     
      
       > combine(int n, int k) { 4         vector
       
        
         > res; 5         vector
         
           nums, temp; 6         for(int i = 0; i < n; i++) 7             nums.push_back(i + 1); 8         cmb(n, k, 0, nums, temp, res); 9         return res;10     }11     void cmb(int n, int k, int idx, vector
          
            nums, vector
           
             &temp, vector
            
             
              > &res){12 if(k && temp.size() == k)13 res.push_back(temp);14 else if(idx < n){15 temp.push_back(nums[idx]);16 cmb(n, k, idx + 1, nums, temp, res);17 temp.pop_back();18 cmb(n, k, idx + 1, nums, temp, res);19 }20 }21 };