算法笔记_面试题_15.回溯算法模板及示例

目录

0. 回溯算法模板

leecode上的相关题目:

1. 组合相关

1.1 组合-77题

1.2 电话号码的字母组合-17题

1.3 组合总和-39题

2. 分割相关

2.1 分割回文串-131题

2.2 复原 IP 地址-93题

3. 子集相关

3.1 不含重复整数的集合的子集(78. 子集)

3.2 含重复整数的数组的子集 (90. 子集 II)

3.3 找出所有子集的异或总和再求和

3.4 统计按位或能得到最大值的子集数目

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

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

• 什么时候输出
• 哪些情况需要跳过

给定两个整数 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]]  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combinations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码: 

class Solution {
public:
    vector result; //可以定义成成员变量,使函数简洁
    vector combine(int n, int k) {
        int startIndex = 1;
        vector path;
        backTracking(n, k, path, startIndex);
        return result;
    }
    void backTracking (int n, int k, vector path, int startIndex) {
        if (k == path.size()) {  //终止条件:当子集数量到达k个时,就可以收集起来,然后返回了.
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i