【LeetCode每日一题】77. 组合 —— DFS算法（C/C++）

写在前面：

没有谁会踏雾而来，喜欢的风景自己去看。

题目：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

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

示例 2：

输入：n = 1, k = 1 输出：[[1]]

提示：

1 <= n <= 20 1 <= k <= n

思路：

更详细的DFS算法请看这篇：DFS详解 + 例题！！！

本文是典型的DFS模板题，并且是最具代表性的例题之一排列组合中的组合题。引用DFS模板，具体需要注意的是，这里某种数字组合的多种排列视为相同情况，因此需“去重”。 一种可行的方案是填数的时候：

（1）如果当前填的是第一个数，则直接填入； （2）在（1）的基础上，后面填入的数都要比前面的数大，因此要进行大小的比较。如果不符合条件，则不能填入。这样既能保证每种组合中数是递增的，也能保证组合是按字典序输出的。

代码：

vector<vector<int>> a; //存储排列数据
vector<int> b; // 存储每次的排列数据 

void DFS(int cur, int n, int k){
          
   
    if(cur == k){
          
   
        a.push_back(b);
        return ; 
    }
    
    for(int i = 1; i <= n; i++){
          
   
        int temp;
        if(cur > 0) temp = b.back();  //返回b数组的最后一个元素
        if((cur == 0) || (cur > 0 && i > temp)){
          
   
            b.push_back(i);
            DFS(cur + 1, n, k);
            b.pop_back();
        }
    }
}

vector<vector<int>> combine(int n, int k) {
          
   
    DFS(0, n, k);
    return a;
}