首页 > itarticle > 77. combinations

77. combinations

admin 11月 18, 2020 0

每日一题 2019 - 04 - 12

题目：

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法：

这个题需要找出 1,2,3....n中任意 k 个数字的组合，且组合不能有重复的元素出现，简单的思路就是回溯法，一方面判断当前已经存在的组合数字的大小是否超过 k 个数字的限制，另一方面需要判断给定的 $$n$$ 个数字是否已经遍历完毕，以及设置合适的递归的结束条件；

代码：

class  {
public:
    void fun( vector<int> &temp ,vector<vector<int> > &now, vector<int> &test , int k ,int begin)
    {
        if(test.size() < k )
        {
            for(int i = begin ; i < temp.size() ; i ++ )
            {
                test.push_back(temp[i]);
                fun(temp,now,test,k,i+1);
                test.pop_back();
            }
        }
        else if(test.size() == k )
        {
            now.push_back(test);
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > now ;
        vector<int> test ; 
        if(k == 0)
        {
            return now ;
        }
        vector<int> temp ; 
        for(int i = 0 ; i < n ; i ++ )
        {
            temp.push_back(i+1) ;
        }
        fun(temp,now,test,k,0);
        return now ;
    }
};