欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【练习题】给定两个整数n和k,返回1 ... n中k个数的所有组合

程序员文章站 2022-07-12 08:53:29
...

例:
For example,
If n = 4 and k = 2, a solution is

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

【练习题】给定两个整数n和k,返回1 ... n中k个数的所有组合
分析题目:例子中,n=4,k=2;

1,2,3,4 两个数一组组合
我们通常的思路就是先选定第一个数,从1开始,然后分别和后面的数组合,1完了,再向后遍历用2去组合
用代码实现也是这个思路

class Solution {
public:
   void findCombine(int index, vector<int>& tmp, const int& n, const int& k, vector<vector<int>>& res){

       if(tmp.size() == k)//组成一组了,插入到vector
        {
            res.push_back(tmp);
            return;
        }
        //最主要的代码
        for(int i = index; i  <= n; i++)
        {
            tmp.push_back(i);
            findCombine(i+1, tmp, n,k, res);
            tmp.pop_back();
        }
        return;
    }
   vector<vector<int>> combine(int n, int k) 
    {
        vector<vector<int>> res;
        if(n < k || n < 1 || k < 1)
            return res;
        vector<int> tmp;
        findCombine(1, tmp, n, k, res);
        return res;
    }
};

【练习题】给定两个整数n和k,返回1 ... n中k个数的所有组合
运用了递归、回溯,当凑够一组时,就回退回去,pop掉一个数,在进行组合
在tmp里,2进出,3进出,用了回溯的思想,进行分别与1组合