今日刷题重点—回溯

文章目录

• • 77. 组合
  • • • 题目描述
      • 示例 1：
      • 示例 2：
      • 思路分析
      • 算法设计
      • 参考代码
  • 216.组合总和III
  • • • 题目描述
      • 示例 1:
      • 示例 2:
      • 思路分析
      • 参考代码
  • 17. 电话号码的字母组合
  • • • 题目描述
      • 示例 1：
      • 示例 2：
      • 示例 3：
      • 思路分析
      • 参考代码

77. 组合

题目描述

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

思路分析

直接的解法是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

n = 100, k = 3 那么就三层for循环，代码如下：

int n = 100;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
            cout << i << " " << j << " " << u << endl;
        }
    }
}

但是如果n为100,k为50,那就是50层for循环,无语住了…
于是,我们可以尝试使用回溯法,本质就是 循环+递归,从而实现多层循环
回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。
由下图可知:元素的个数n等于树的宽度,k等于树的深度

算法设计

• 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

• 图中每次搜索到了叶子节点，我们就找到了一个结果。

• 只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

卡尔大佬的回溯法三部曲

• 递归函数的返回值以及参数
  这里直接使用全局变量来操作,一个存放最终的结果集,一个存放符合条件的临时集合.这样我们也就不需要返回值了.
  参数:数据个数n,组合个数k 每次需要传入.另外也需要传入下次循环的起始位置,方便下一次其他数据进行组合.

vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
...
}

• 回溯函数终止条件
  当path.size() == k了,则说明我们已经找到了大小为k的组合了. 结束递归

if(path.size()==k){
	result.push_back(path);
	return;//结束递归 
}

• 单层搜索过程
  回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
  
  for循环每次从startIndex开始遍历，然后用path保存取到的节点i,递归回来之后进行回溯,继续循环.

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点 
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

代码优化
可以剪枝的地方在递归中每一层的for循环条件处。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

• 已经选择的元素个数：path.size();
• 还需要的元素个数为: k - path.size();
• 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
  为什么有个+1呢，因为包括起始位置。
  所以中间for循环的条件可以改造为:i <= n-(k-path.size())+1

参考代码

#include<bits/stdc++.h>
using namespace std;

vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int startIndex){
	if(path.size()==k){
		result.push_back(path);
		return;//结束递归 
	}
//	for(int i = startIndex; i <= n;i++){//未剪枝 
	for(int i = startIndex; i <= n-(k-path.size())+1;i++){	//剪枝 
		path.push_back(i);//存放i元素
		backtracking(n,k,i+1);//减小可选择返回,继续递归
		path.pop_back();//弹出当前元素,进行回溯 
	}
}

vector<vector<int>> combine(int n, int k) {
	backtracking(n,k,1);
	return result;
}

216.组合总和III

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

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

示例 2:

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

思路分析

本题相对于上个题只是多个 之和为n的限制,其他的处理思路和上题类似
转为树形图就是:k相当于树的深度. 1-9 相当于树的宽度

下面开始我们熟悉的回溯三部曲

• 确定递归参数和返回值
  递归参数:每次需要传入组合的位数 k,循环的下一个位置下标 index,当前组合数的和 sum,目标值 targetSum
• 确定递归的结束条件
  当path.size()==k时结束递归.但同时满足sum == targetSum,当前组合数才被加入到结果集中
• 确定单层递归的逻辑
  先循环,加入元素,之后继续递归,递归之后进行回溯,回溯完毕进入下一次循环

算法剪枝

• 如果后序可选择的元素+当前组合数元素 小于 k,则没必要继续寻找了
• 如果组合数的和已经大于targetSum,则没必要再去寻找了.

参考代码

#include<bits/stdc++.h>
using namespace std;

vector<int> path;
vector<vector<int>> result;

void backtracking(int k,int startIndex,int sum,int targetSum) {
	if(sum>targetSum) {//剪枝
		return;
	}
	if(path.size()==k) {
		if(sum==targetSum) {
			result.push_back(path);
		}
		return;//结束递归
	}
//	for(int i = startIndex; i <= n;i++){
	for(int i = startIndex; i <= 9-(k-path.size())+1; i++) { //此时还需要的元素大小   &&
		path.push_back(i);//存放i元素
		backtracking(k,i+1,sum+i,targetSum);//减小可选择返回,继续递归 这里返回的是i+1哦,和startIndex无关..
		path.pop_back();//弹出当前元素,进行回溯
	}
}

vector<vector<int>> combinationSum3(int k, int n) {
	backtracking(k,1,0,n);
	return result;
}

17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

思路分析

输入：“23”，抽象为树形结构，如图所示：

图中可以看出遍历的深度就是输入的 字符串的长度，而叶子节点就是我们要收集的结果，宽度为 字符所对应的字符串长度 ,如2==>abc

回溯三部曲

• 确定递归参数和返回值
  参数:需要传入输入的字符串digits,当前递归到的digits的index
  返回值:依旧定义两个个全局变量,一个是最终结果集,一个存放临时组合数.所以返回值为void 可以看出回溯类型的递归通常没有返回值
• 确定递归结束条件
  如果index==digits.size(),则说明已经找到了满足的组合数,递归结束
• 确定单层递归逻辑
  先从递归的index拿到对应的字符串,然后开始循环,递归,回溯…

参考代码

vector<string> result;
string s;
string  arr[10] = {
	"",//0
	"",//1
	"abc",//2
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz",
};

void backtracking(string& digits,int index) {//digits:记录输入的数字  ,index:遍历前面的数字
	if(digits.size()==index) {
		result.push_back(s);
		return;
	}
	int num = digits[index] - '0';
	string temp = arr[num];
	for(int i = 0; i < temp.size(); i++) { //每层遍历的都是digits中的元素  递归树的深度就是digits.size()大小
		s.push_back(temp[i]);
		backtracking(digits,index+1);
		s.pop_back();
	}
}
vector<string> letterCombinations(string digits) {//digits.size()==>k 循环次数
	if(digits=="") {//注意digits为空的情况 
		return result;
	}
	backtracking(digits,0);
	return result;
}

---

如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客