Day 8:77 组合

77 组合

• 1. 题目描述
• 2. 解题思路
• 3. 代码实现
• 4. 回溯模板

1. 题目描述

77 组合

2. 解题思路

该题可以使用回溯类型的模板来解决，注意到可以进行剪枝操作。

3. 代码实现

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> combine(int n, int k) {
        function<void(int)> dfs = [&](int idx) {
            // 剪枝
            if (path.size() + (n - idx + 1) < k) {
                return;
            }
            // if (idx == n + 1) {
            //     return;
            // }
            if (path.size() == k) {
                res.push_back(path);
                return;
            }
            // 选
            path.push_back(idx);
            dfs(idx + 1);
            path.pop_back();
            // 不选
            dfs(idx + 1);
        };
        dfs(1);
        return res;
    }
};

4. 回溯模板

回溯三部曲

1. 递归函数的返回值以及参数；
2. 回溯函数终止条件；
3. 单层搜索的过程。

void backtracking(参数) {
   if (终止条件) {
       存放结果;
       return;
   }

   for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
       处理节点;
       backtracking(路径，选择列表); // 递归
       回溯，撤销处理结果
   }
}