Leetcode 77. 组合

题目

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

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

思路

• 递归函数的返回值以及参数
  在这里需要定义两个全局变量，一个用来存放符合条件的单一结果，一个用来存放符合条件结果的集合。对于递归函数，我们需要传入参数n,k。更重要的是传入参数startindex,该参数表示记录本层递归中集合从哪里开始遍历。在集合[1,2,3,4]中取出1之后，下一层递归就要开始在[2,3,4]中取数字了。

• 回溯函数的终止条件
  当path数组的大小是k，代表达到所谓的叶子节点，此时用result数组将path数组保存起来，终止本层递归

• 单层搜索的过程
  回溯法的搜索过程就是一个树型结构的遍历过程，for循环用来横向遍历，递归的过程就是纵向遍历。for循环每次从startindex开始遍历，然后用Path保存取到的节点I,递归函数backtracking不停的调用自己，向深处遍历，遇到叶子节点就开始返回上一层，然后开始回溯操作，撤销本次处理的结果。

代码

class Solution {
public:
    vector<int> path;// 用来存放符合条件的结果  记录每一种组合  其实就是二叉树的路径
    vector<vector<int>> result;//存放符合条件的结果的集合

    void backtracking(int n,int k,int startindex)
    {
        // n代表集合大小 k代表从集合n中取k个元素
        // startindex 代表用于每次选择元素范围大小的调整
        if(path.size() == k)
        {
            // 当path的大小是k的时候  代表到达了叶子节点  存放结果 并且结束本层的递归 准备回溯
            result.push_back(path);
            return;
        }

        // 控制单层集合的遍历  横向遍历
        for(int i = startindex; i <= n; i++)
        {
            path.push_back(i);
            backtracking(n,k,i + 1);// 控制树的纵向遍历  下一层搜索要从i + 1开始
            path.pop_back();// 回溯 撤销处理的节点  接着寻找下一种结果
        }
    }

    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n,k,1);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33