LeetCode-回溯

Last updated on 3 months ago

​ 回溯 -》 穷举

  • 回溯函数模板返回值以及参数

  • 回溯函数终止条件

  • 回溯搜索的遍历过程

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void backtracking(参数) {
        if (终止条件) {
            存放结果;
            return;
        }

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

    1. 组合

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

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

    思路： 数字中有多少中组合，k为2的话，两个for可以解决，k为为100 就不能这么做了

    首先 ：

    • 回溯函数的模版是怎样的

      ​ 不需要返回值，参数需要 知道哪里开始，哪里结束，截止需要的条件

    • 终止条件

      ​ 回溯拿到k个数的时候即停止

    • 就改题而言过程是要遍历每个数，即一for循环加上回溯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> res;  //最终结果保存的地方
    vector<int> path;  //每一轮回溯结果保存的地方
    void back(int n,int k,int index){ //n 哪里结束，k 截止需要的条件，index 其实的地方
        if(path.size() == k){    //当path 满足 k 个时候就可以保存到 res中
            res.push_back(path);
            return;
        }
        for(int i = index; i <= n ;i++){   // 遍历每个数  每个数都可能做为第一个数
            path.push_back(i);            //保存
            back(n,k,i+1);  			 // i+1 意思是下一轮从下一个数开始
            path.pop_back();              //满足条件了，就出栈，腾出空间给下个数
        }
    }
    vector<vector<int>> combine(int n, int k) {
        back(n,k,1); //
        return res;
    }
};

2. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

  • 和上题差不多，1到9的数字总，k个组合的数之和为n

还是来三部曲：

  • 回溯函数的参数 

    1
    back(int target,int k,int index,int sum) //k 为组合个数，target 组合之和，index 起始的地方，sum 记录总和

  • 终止条件

    组合个数位k，并且呢 组合之和为 target

  • 搜索过程

    还是遍历，就是遍历计数时 还要记录总和sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;  //最终结果保存的地方
    vector<int> path;  //每一轮回溯结果保存的地方
    void back(int target,int k,int index,int sum){
        if(path.size() == k){    //当path 满足 k 个时，sum 等于 target
            if(sum == target)
                res.push_back(path);
            return;
        }
        for(int i = index; i <= 9 ;i++){   // 遍历每个数  每个数都可能做为第一个数
            path.push_back(i);            //保存
            sum = sum + i;				//这里计算总和
            back(target,k,i+1,sum);  			
            path.pop_back();              //出栈了，总和也要
            sum = sum -i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        int sum = 0;
        back(n,k,1,sum);
        return res;
    }
};