数据结构与算法-回溯法

回溯法思路

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

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

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

回溯法题目

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;
}
};

组合总和II

解题思路

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

组合总和III

参考资料

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