数据结构与算法-回溯法

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 2.8k | 阅读时间 ≈ 13

回溯法思路

解决回溯问题需要思考3个问题：

  1. 路径：也就是已经做出的选择。
  2. 选择列表：也就是你当前可以做的选择。
  3. 结束条件：也就是到达决策树底层，无法再做选择的条件。
1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

回溯法题目

17.电话号码的组合

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

解题思路

结束条件是字符串长度和输入字符串一样，选择列表有当前数字代表的几个字符

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
class Solution {
public:
    string str;
    vector<string> ans;
    void backtracking(string digits, unordered_map<char, string>& m, int idx_s){
        if (idx_s == digits.size()){
            ans.push_back(str);
            return;
        }
        
        int num = m[digits[idx_s]].size();
        for (int i = 0; i < num; i++){
            str.push_back(m[digits[idx_s]][i]);
            backtracking(digits, m, idx_s+1);
            str.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return ans;
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        backtracking(digits, phoneMap, 0);
        return ans;
    }
};

22.括号生成

问题描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：
1 <= n <= 8

解题思路

终止条件是字符串的size到了n*2，可以做的选择是添加左括号或者右括号，这里还需要分别判断一下是否可以添加左或者右括号。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    vector<string> ans;
    string str;
    bool canRightPana(string s){
        int n = s.size();
        if (n == 0) return false;
        int left = 0;
        int right= 0;
        for (char c : s){
            if (c == '(')
                left++;
            else
                right++;
        }
        if (left > right)
            return true;
        return false;
    }
    
    bool canLeftPana(string s, int n){
        int m = s.size();
        if (m == 0) return true;
        int left = 0;
        int right= 0;
        for (char c : s){
            if (c == '(')
                left++;
            else
                right++;
        }
        if (left >= n)
            return false;
        return true;
    }
    void backtracking(int n, int i){
        if (i == n*2){
            ans.push_back(str);
            return;
        }

        bool canRight = canRightPana(str);
        bool canLeft  = canLeftPana(str, n);
        if (canLeft){
            str.push_back('(');
            backtracking(n, i+1);
            str.pop_back();
        }

        if (canRight){
            str.push_back(')');
            backtracking(n, i+1);
            str.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        backtracking(n, 0);
        return ans;
    }
};

看了下题解发现其实判断能否添加左右括号还可以写得更简单些，直接在回溯函数的参数里面加上左右括号的数量就方便很多了。

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
class Solution {
public:
    vector<string> ans;
    string str;
    void backtracking(int n, int left, int right){
        if (str.size() == n * 2){
            ans.push_back(str);
            return;
        }
        if (left < n){
            str.push_back('(');
            backtracking(n, left+1, right);
            str.pop_back();
        }
        if (right < left){
            str.push_back(')');
            backtracking(n, left, right+1);
            str.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        backtracking(n, 0, 0);
        return ans;
    }
};

77.组合

问题描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

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

解题思路

终止条件是当前做得选择数组的大小等于k，选择就是把当前的数放入到数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    vector<int> vec;
    vector<vector<int>> res;
public:
    void backtracking(int n, int k, int StartNum){
        if (vec.size() == k){
            res.push_back(vec);
            return;
        }
        for (int i = StartNum; i <= n; i++){
            vec.push_back(i);
            backtracking(n, k , i+1);
            vec.pop_back();
        }
        
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
};

78.子集

问题描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题思路

终止条件是idx到达了nums的size，做的选择有将当前数加入选择数组或者不加入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    vector<int> vec;
    vector<vector<int>> res;
public:
    void backtracking(vector<int>& nums, int idx){
        if (idx == nums.size()){
            res.push_back(vec);
            return;
        }

        vec.push_back(nums[idx]);
        backtracking(nums, idx+1);
        vec.pop_back();
        backtracking(nums,idx+1);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }
};

39.组合总和

问题描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

解题思路

先确定终止条件，当选择当前选择数组的和等于零的时候，就将它push到结果数组中。因为每个数是可以重复选择的，所以先一直选择一个数，直到他们的和大于的target，然后再选择后面的数。

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
class Solution {
private:
    vector<int> vec;
    vector<vector<int>> res;
public:
    void backtracking(vector<int>& candidates, int target, int idx){
        if (target == 0){
            res.push_back(vec);
            return;
        }
        if (idx == candidates.size())
            return;
        
        if (target - candidates[idx] >= 0){
            vec.push_back(candidates[idx]);
            backtracking(candidates, target - candidates[idx], idx);
            vec.pop_back();
        }
        backtracking(candidates, target, idx + 1);
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0);
        return res;
    }
};

40.组合总和II

解题思路

题目基本和组合总和I相同，唯一不同的就是一个数只能用一次，并且候选数中会有重复的数字。

216.组合总和III

46.全排列

问题描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解题思路

使用一个数组来保存每个数字的状态，判断一个数字有没有被使用。

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
class Solution {
public:
    vector<int> vec;
    vector<bool> status;
    vector<vector<int>> res;
    void backtrack(vector<int>& nums){
        if (vec.size() == nums.size()){
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (status[i]){
                vec.push_back(nums[i]);
                status[i] = false;
                backtrack(nums);
                vec.pop_back();
                status[i] = true;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        status.resize(nums.size(), true);
        backtrack(nums);
        return res;
    }
};

47.全排列II

问题描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

解题思路

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
class Solution {
public:
    vector<bool> status;
    vector<int> vec;
    vector<vector<int>> res;
    void backtracking(vector<int>&nums){
        if (vec.size() == nums.size()){
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (status[i]){
                if (i != 0 && nums[i] == nums[i-1] && status[i-1])
                    continue;
                vec.push_back(nums[i]);
                status[i] = false;
                backtracking(nums);
                vec.pop_back();
                status[i] = true;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        status.resize(nums.size(), true);
        sort(nums.begin(), nums.end());
        backtracking(nums);
        return res;
    }
};

最大兼容性评分和

leetcode第251场周赛第三题，终于有能做出来第第三题了。

问题描述

有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。

这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。

每个学生都会被分配给 一名 导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。

例如，学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。
请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。

给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。

示例 1：
输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
输出：8
解释：按下述方式分配学生和导师：

  • 学生 0 分配给导师 2 ，兼容性评分为 3 。
  • 学生 1 分配给导师 0 ，兼容性评分为 2 。
  • 学生 2 分配给导师 1 ，兼容性评分为 3 。
    最大兼容性评分和为 3 + 2 + 3 = 8 。

示例 2：
输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
输出：0
解释：任意学生与导师配对的兼容性评分都是 0 。

解题思路

问题描述很复杂，其实把问题简化一下就是，先求出每个学生和老师之间的兼容性评分，然后再找出能让总评分最高的分数。求学生老师之间的分数很简单。然后就是求最高的分数，最笨的办法就是把所有学生和老师之间可能的排列组合列出来，找到最高分数。排列组合就可以用回溯法了。（不知道有没有其他更快的方法）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int maxScore;
    vector<pair<int, int>> ans;
    void backtrack(vector<vector<int>>& score, vector<bool>& mentorList, int stuNum, int m){
        if (ans.size() == m){
            int curScore = 0;
            for (int i = 0; i < m; i++){
                int a = ans[i].first;
                int b = ans[i].second;
                curScore += score[a][b];
            }
            if (curScore > maxScore)
                maxScore = curScore;
            return;
        }
        
        for (int i = 0; i < m; i++){
            if (mentorList[i]){
                ans.push_back(make_pair(stuNum, i));
                mentorList[i] = false;
                backtrack(score, mentorList, stuNum+1, m);
                mentorList[i] = true;
                ans.pop_back();
            }
        }
        
    }
    
    
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        maxScore = 0;
        int m = students.size();
        int n = students[0].size();
        vector<vector<int>> score(m, vector<int> (m,0));
        for (int i = 0; i < m; i++){
            for (int j = 0; j < m; j++){
                for (int k = 0; k < n; k++){
                    score[i][j] += (students[i][k] == mentors[j][k]);
                }
            }
        }
        
        vector<bool> mentorList(m, true);
        backtrack(score, mentorList, 0, m);
        return maxScore;
        
    }
};

参考资料

https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban