递归用来纵向遍历，for 循环用来横向遍历，start 表示组合的起始位置
- 给定数组中是否有重复的数字，是否需要去重
- 每个数字在每个组合中能否重复使用（决定递归传入参数是否 +1）
给定数组没有重复数字，在横向遍历过程中不能取相同的数
- 解题方法：
递归的参数：n，k（题目已知），path，res（全局变量），start 递归的起始位置
递归终止条件：到叶子节点记录答案，递归终止
单层递归逻辑：把这一层的数遍历一遍并加入路径，递归下一层（下一层的起始位置下标 +1），回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
dfs(n, k, 1);
return res;
}
void dfs(int n, int k, int start){
if (k == path.size()){
res.push_back(path);
return;
}
for (int i = start; i <= n; i ++){
path.push_back(i);
dfs(n, k, i + 1);
path.pop_back();
}
}
};
给定两个整数
你可以按 任何顺序 返回答案。
数据范围
输入样例
4 2
输出样例
1 2
1 3
1 4
2 3
2 4
3 4
- 解题代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 20;
int n, k;
vector<int> path;
void dfs(int n, int k, int start){
if (k == path.size()){
for (auto c: path) cout << c << ' ';
puts("");
return;
}
for (int i = start; i <= n; i ++){
path.push_back(i);
dfs(n, k, i + 1);
path.pop_back();
}
}
int main(){
cin >> n >> k;
dfs(n, k, 1);
return 0;
}
给定数组没有重复数字，在横向遍历过程中不能取相同的数
- 解题方法：
递归的参数：n，k（题目已知），path，res（全局变量），start 递归的起始位置，sum 当前总和为多少
递归终止条件：到叶子节点且总和等于 sum 记录答案，递归终止
单层递归逻辑：把这一层的数遍历一遍并加入路径，更新 sum 并递归下一层（下一层的起始位置下标 +1），回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1, 0);
return res;
}
void dfs(int k, int n, int start, int sum){
if (k == path.size() && sum == n){
res.push_back(path);
return;
}
for (int i = start; i <= 9; i ++){
path.push_back(i);
sum += i;
dfs(k, n, i + 1, sum);
sum -= i;
path.pop_back();
}
}
};
给定数组没有重复数字，在横向遍历过程中不能取相同的数
- 解题方法：先用哈希表存所有字母的数字索引
递归的参数：digits（题目已知），index（当前取了多少个字母）
递归终止条件：当前取的字母和 digits 的大小数量相等的时候记录答案终止递归
单层递归逻辑：在哈希表中找到当前对应的字母组合，遍历当前字母组合，记录路径，递归下一层，回溯 - leetcode解题代码
class Solution {
public:
string map[10] = {
"", "",
"abc", "def",
"ghi", "jkl","mno",
"pqrs", "tuv", "wxyz"
};
vector<string> res;
string path;
vector<string> letterCombinations(string digits) {
if (digits.empty()) return res;
dfs(digits, 0);
return res;
}
void dfs(string digits, int index){
if (index == digits.size()){
res.push_back(path);
return;
}
int digit = digits[index] - '0';// 将字符串转换为数字
string letter = map[digit];// 在map当中找数字对应的字母
for (int i = 0; i < letter.size(); i ++){
path.push_back(letter[i]);
dfs(digits, index + 1);
path.pop_back();
}
}
};
给定数组没有重复数字，在横向遍历过程中可以取相同的数
- 解题方法：
递归的参数：candidates，target（题目已知），path，res（全局变量），start 递归的起始位置，sum 当前总和为多少
递归终止条件：总和等于 sum 记录答案，递归终止
由于可能遍历到数组结尾都没找到等于 sum 的数组，导致栈溢出
又因为所有数都是正整数，当超过了 sum，说明不可能找到等于 sum 的组合，递归终止
单层递归逻辑：把这一层的数遍历一遍并加入路径，递归下一层（数可以重复使用），回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, int sum, int start){
if (sum > target) return;
if (sum == target){
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i ++){
sum += candidates[i];
path.push_back(candidates[i]);
// 由于同一个数字可以无限制重复被选取，在当前层取了这个数，递归到下一层依然可以取这个数
dfs(candidates, target, sum, i);
path.pop_back();
sum -= candidates[i];
}
}
};
给定数组有重复数字，在横向遍历过程中不能取相同的数
- 解题方法：
递归的参数：candidates，target（题目已知），path，res（全局变量），start 递归的起始位置，sum 当前总和为多少
递归终止条件：总和等于 sum 记录答案，递归终止
由于可能遍历到数组结尾都没找到等于 sum 的数组导致栈溢出
又因为所有数都是正整数，所以当总和超过了 sum，说明不可能找到等于 sum 的组合，递归终止
单层递归逻辑：同一层不能选相同的元素
把这一层的数遍历一遍并加入路径，递归下一层（数可以重复使用），回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, int sum, int start){
if (sum > target) return;
if (sum == target){
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i ++){
if (i > start && candidates[i] == candidates[i - 1])
continue;
sum += candidates[i];
path.push_back(candidates[i]);
dfs(candidates, target, sum, i + 1);
path.pop_back();
sum -= candidates[i];
}
}
};
递归用来纵向遍历，for 循环用来横向遍历，start 表示切割线的位置
- 链接https://leetcode.cn/problems/palindrome-partitioning/
- 解题方法：
定义回文串
递归的参数：s（题目已知），start（切割线位置）
递归终止条件：切割线位置移动到字符串的末尾递归结束
单层递归逻辑：遍历当前字符串组合判断是否是回文串，如果是回文串，将这一段切割加入路径，递归到下一个层，回溯 - leetcode解题代码
class Solution {
public:
bool HuiWen (string s, int l, int r){
for (int i = l, j = r; i < j; i ++, j --){
if (s[i] != s[j]) return false;
}
return true;
}
vector<vector<string>> res;
vector<string> path;
vector<vector<string>> partition(string s) {
dfs(s, 0);
return res;
}
void dfs(string s, int start){
if (start == s.size()){
res.push_back(path);
return;
}
for (int i = start; i < s.size(); i ++){
if (HuiWen(s, start, i)){
string str = s.substr(start, i - start + 1);
path.push_back(str);
}
else continue;
dfs(s, i + 1);
path.pop_back();
}
}
};
- 链接https://leetcode.cn/problems/restore-ip-addresses/
- 解题方法：
判断合法性（没有前导 0，没有特殊字符，整数大小不超过 255）
递归的参数：s（题目已知），start（切割线位置），point 逗点个数
递归终止条件：逗点个数等于 3 且从切割线位置到当前位置这一段是合法的，则加入答案
单层递归逻辑：从切割线开始遍历，如果从切割线位置到当前位置这一段合法，在其后面添加逗点，递归到下一层（由于添加了逗点，所以 i+2），回溯 - leetcode解题代码
class Solution {
public:
bool isValid(string s, int l, int r){
if (l > r) return false;
if (s[l] == '0' && l != r) return false;
int num = 0;
for (int i = l; i <= r; i ++){
if (s[i] < '0' || s[i] > '9') return false;
num = num * 10 + (s[i] - '0');
if (num > 255) return false;
}
return true;
}
vector<string> res;
vector<string> restoreIpAddresses(string s) {
dfs(s, 0, 0);
return res;
}
void dfs(string s, int start, int point){
if (point == 3 && isValid(s, start, s.size() - 1)){
res.push_back(s);
return;
}
for (int i = start; i < s.size(); i ++){
if (isValid(s, start, i)){
s.insert(s.begin() + i + 1, '.');
point ++;
dfs(s, i + 2, point);
point --;
s.erase(s.begin() + i + 1);
}
else break;
}
}
};
子集问题和组合分割问题的区别是，子集需要返回所有节点，而不是遍历到叶子节点再返回（在递归终止条件，和将路径加入答案有所不同）
给定数组没有重复数字
- 解题方法：
递归的参数：nums（题目已知），start（子集的起始位置） 递归终止条件：子集的起始位置超过数组的长度，返回所有节点
单层递归逻辑：从子集的起始位置开始遍历，递归到下一层，回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return res;
}
void dfs(vector<int>& nums, int start){
if (start > nums.size()) return;
res.push_back(path);
for (int i = start; i < nums.size(); i ++){
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};
给定数组有重复数字
- 解题方法：
递归的参数：nums（题目已知），start（子集的起始位置）
递归终止条件：子集的起始位置超过数组的长度，返回
单层递归逻辑：从子集的起始位置开始遍历，如果取到重复元素了则跳过，递归到下一层，回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, 0);
return res;
}
void dfs(vector<int>& nums, int start){
if (start > nums.size()) return;
res.push_back(path);
for (int i = start; i < nums.size(); i ++){
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};
给定数组有重复数字，且不能改变原来数组的顺序
- 解题方法：
本题不能先排序，排序就改变了题意，本题需要用一个哈希集合来维护不重复元素
递归的参数：nums（题目已知），start（子集的起始位置）
递归终止条件：子集的起始位置超过数组的长度，返回
单层递归逻辑：从子集的起始位置开始遍历，如果路径为空或满足递增子序列且当前元素没有在哈希集合中出现过则取当前元素，否则跳过，递归到下一层，回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(nums, 0);
return res;
}
void dfs(vector<int>& nums, int start){
if (start > nums.size()) return;
if (path.size() >= 2) res.push_back(path);
unordered_set<int> set;
for (int i = start; i < nums.size(); i ++){
if (path.empty() || nums[i] >= path.back()){
if (set.count(nums[i])) continue;
set.insert(nums[i]);
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
}
};
排列问题和组合问题的区别在于不需要 start 标记下一个数的位置，而需要一个 bool 数组标记当前数是否使用过而不能重复使用，排列问题也是到叶子节点再添加答案并返回
给定数组没有重复数字
- 解题方法：
递归的参数：nums（题目已知），flag（记录当前元素是否被使用过） 递归终止条件：路径长度等于数组长度（叶子节点）记录答案并返回
单层递归逻辑：从 0 开始遍历，如果当前元素没有被选过则取当前元素，否则跳过，记录当前元素被使用过了，递归到下一层，回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> flag(nums.size(), false);
dfs(nums, flag);
return res;
}
void dfs(vector<int>& nums, vector<bool> flag){
if (path.size() == nums.size()){
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i ++){
if (flag[i] == true) continue;
flag[i] = true;
path.push_back(nums[i]);
dfs(nums, flag);
path.pop_back();
flag[i] = false;
}
}
};
给定数组有重复数字
- 解题方法：
同一层不能选取同样的元素，与组合问题类似，先排序保证相邻元素不重复
递归的参数：nums（题目已知），flag（记录当前元素是否被使用过）
递归终止条件：路径长度等于数组长度（叶子节点）记录答案并返回
单层递归逻辑：从 0 开始遍历，如果上一个元素没有被选过且当前元素和上一个元素是重复元素则跳过，如果当前元素被选过也跳过，否则记录当前元素被使用过了，递归到下一层，回溯 - leetcode解题代码
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> flag(nums.size(), false);
dfs(nums, flag);
return res;
}
void dfs(vector<int>& nums, vector<bool> flag){
if (path.size() == nums.size()){
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i ++){
if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false) continue;
if (flag[i] == true) continue;
flag[i] = true;
path.push_back(nums[i]);
dfs(nums, flag);
path.pop_back();
flag[i] = false;
}
}
};