[数据结构与算法]LeetCode刷题day45

今日刷题重点—回溯算法

39. 组合总和

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

思路分析

这个和 LeetCode77 组合的区别在于本题中数字的数量是无限的,每个数字可以被重复选取.所以我们只需要在回溯的时候,下一次回溯的开始index可以从当前结束index开始.

老样子,走一遍 回溯三部曲

• 确定递归参数和返回值
  递归参数:每次需要传入组合的位数 k,循环的下一个位置下标 index,当前组合数的和 sum,目标值 targetSum.
  由于我们使用全局变量来保存结果值,所以并不需要定义返回值.
• 确定递归的结束条件
  当sum>=targetSum时,结束递归. 当 =时,还要将其加入到结果集中
• 确定单层递归的逻辑
  先横向循环,加入组合的元素,之后继续递归,递归回来之后回溯,回溯完毕之后进入下一次循环.

代码剪枝
剪枝的话可以先对数组排个序,这样我们可以在循环条件判断时稍作文章,如果当前循环数和已经找到的组合数之和大于targetSum,则该数不必进入回溯函数了,当然由于排过序,越往后值会更大,循环可以直接结束,往回回溯!

参考代码(未剪枝)

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

void backtracking(vector<int>& candidates,int startIndex,int sum,int targetSum){
	if(sum>targetSum){
		return;
	}else if(sum==targetSum){
		result.push_back(path);
		return;
	}
	for(int i = startIndex; i<candidates.size() ;i++){
		sum+=candidates[i];
		path.push_back(candidates[i]);
		backtracking(candidates,i,sum,targetSum);
		path.pop_back();
		sum-=candidates[i];
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	backtracking(candidates,0,0,target);
	return result;
}

参考代码2(剪枝)

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

void backtracking(vector<int>& candidates,int startIndex,int sum,int targetSum){
	if(sum==targetSum){
		result.push_back(path);
		return;
	}
	for(int i = startIndex; i<candidates.size() &&(sum+candidates[i] <= targetSum);i++){
		sum+=candidates[i];
		path.push_back(candidates[i]);
		backtracking(candidates,i,sum,targetSum);
		path.pop_back();
		sum-=candidates[i];
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	sort(candidates.begin(),candidates.end());
	backtracking(candidates,0,0,target);
	return result;
}

40. 组合总和 II

题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

思路分析

本题要是仅凭读题感觉好像比上一题还简单,但是看过示例之后就会发现,是我太天真了!😱😱😱 主要有如下区别:

• 本题candidates中的每个数字在每个组合中只能使用一次
• 本题数组candidates的元素是有重复的,而 39 组合总和 是无重复的数组

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

很容易想到的思路:把所有组合求出来，再用set或者map去重，但这么做很容易超时！

组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。 (同一树枝:也就是组合中数的维度,组合中的数可以有重复的. 同一树层:数组中数循环的维度,由于数组有重复数,所以上次可以循环到这个数,下次循环也可以到这个数,但是这俩数是在同一for循环内的.)

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

去重之前,我们需要对数进行排序.(为什么排序,大家可以思考一下)

树形结构如图所示

used数组存储的是本层数的使用情况, 用于判断是否是同一个树层

算法设计

??????回溯三部曲

• 确定递归函数参数和返回值
  每次需要传入数组candidates,循环的下一个位置下标 startIndex,当前组合数的和 sum,目标值 targetSum,以及用于去树层重的used数组
  由于我们使用全局变量来保存结果值,所以并不需要定义返回值.
• 确定递归终止条件
  当sum>=targetSum时,结束递归. 当 = 时,还要将其加入到结果集中(由于后序会有剪枝操作,所以sum>targetSum可以省略)
• 确定单层递归逻辑
  先判断当前数和上一个是否是同一个树层,如果是则跳过该数,循环下一个数. 否则更新sum,path数组,继续递归,递归完毕之后进行回溯,再继续判断循环下一个数.

??????本题核心就是去重: candidates[i] == candidates[i - 1]

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过,不必去重
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过,需要去重

🌟🌟🌟代码剪枝:本题剪枝方案和上题类似

参考代码1

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

void backtracking(vector<int>& candidates,int startIndex,int sum,int targetSum,vector<bool>& used) {
//	if(sum>targetSum){
//		return;
//	}else if(sum==targetSum){
//		result.push_back(path);
//		return;
//	}
	if(sum==targetSum) {
		result.push_back(path);
		return;
	}
	for(int i = startIndex; i<candidates.size() &&(sum+candidates[i] <= targetSum); i++) {
		if(i>0 &&candidates[i]==candidates[i-1]&&used[i-1]==false) { //同一层的被重复使用过,直接进入下一个
			continue;
		}
		sum+=candidates[i];
		path.push_back(candidates[i]);
		used[i] = true;
		backtracking(candidates,i+1,sum,targetSum,used);
		path.pop_back();
		sum-=candidates[i];
		used[i] = false;
	}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	vector<bool> used(candidates.size(),false);
	sort(candidates.begin(),candidates.end());
	backtracking(candidates,0,0,target,used);
	return result;
}

参考代码2(用startIndex去重)

void backtracking(vector<int>& candidates,int startIndex,int sum,int targetSum) {
	if(sum==targetSum) {
		result.push_back(path);
		return;
	}
	for(int i = startIndex; i<candidates.size() &&(sum+candidates[i] <= targetSum); i++) {
		if(i>startIndex &&candidates[i]==candidates[i-1]) { //同一层的被重复使用过,直接进入下一个
			continue;
		}
		sum+=candidates[i];
		path.push_back(candidates[i]);
		used[i] = true;
		backtracking(candidates,i+1,sum,targetSum);
		path.pop_back();
		sum-=candidates[i];
		used[i] = false;
	}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	sort(candidates.begin(),candidates.end());
	backtracking(candidates,0,0,target);
	return result;
}

131. 分割回文串

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

思路分析

本题这涉及到两个关键问题：

• 切割问题，有不同的切割方式
• 判断回文

切割问题类似组合问题

对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。

• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。

?????? 注意: 组合的index是选取的组合数的下标位置.而切割的index是切割位置数的index,但是实际位置却是index+1,所以下一次传入的将是index+1.

树形结构图
如图所示 index=0,切割位置1,下一轮传入的也是1,当所有的切割完毕,下一次传入的是 arr.size().这个将作为递归的结束条件

算法设计

• 确定递归函数参数和返回值
  参数:递归的字符串s,每层递归的startIndex
  全局变量path存放切割后的回文子串,result存放结果集,所以不需要返回值.
• 确定递归结束条件
  如果起始位置已经>=s的大小，说明已经找到了一组分割方案了,结束递归即可
• 确定单层递归逻辑
  首先判断这个子串[startIndex,i]是不是回文，如果是回文，就加入在vector<string> path中,然后递归,完毕后回溯. 如果不是则 i++ 判断下一个…

回文串的判断我们可以使用双指针法或者反转字符串进行比较的方法

参考代码

vector<vector<string>> result;
vector<string> path;
void backtracking(string& s,int startIndex){//startIndex切割位置 
	if(startIndex>=s.size()) {
		result.push_back(path);
		return;
	}
	for(int i = startIndex; i<s.size();i++){
		if(isPalindrome(s,startIndex,i)){//切割域: [startInde,i] i为切割所包含的最后一个元素下标, 真正的切割是在i+1处,单不包含i+1这个元素 
			string temp = s.substr(startIndex,i-startIndex+1) ;
			path.push_back(temp); 
			backtracking(s,i+1);//从i+1开始继续切割 
			path.pop_back(); 
		}else{
			continue;//不满足则寻找其他的切割点 
		}
	}
}

bool isPalindrome(string& s,int l,int r){//判断是否回文 
	while(l<=r){
		if(s[l++]!=s[r--]){
			return false;
		}
	}
	return true;
}

vector<vector<string>> partition(string s) {
	backtracking(s,0);
}

93. 复原 IP 地址

题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

思路分析

这个题和上文的分割回文串很相似,先截取,再判断,符合则进行继续递归

?????? 回溯三部曲

• 确定递归参数和返回值
  参数:目标串s,搜索的起始位置startIndex,添加 .的数量pointNum
  返回值:因为使用了全局变量保存结果,所以无需返回值.
• 确定递归结束条件
  本题虽然说是用三个.做分割,但是也要判断最后一段是否是合格串
• 确定单层递归逻辑
  先判断是否是合格串,如果是则添加点. 然后递归,回溯,进行下一轮循环. 如果不是,则直接 i++…

💥💥💥合格串需要满足的条件

• 段位以0为开头的数字不合法
• 段位里有非正整数字符不合法
• 段位如果大于255了不合法

参考代码

vector<string> result;
void backtracking(string& s,int startIndex,int pointNum){
	if(pointNum==3){
		//判断第四段是否符合
		if(isValid(s,startIndex,s.size()-1)) {
			result.push_back(s);
		}
		return;
	} 
	for(int i = startIndex; i < s.size();i++){
		if(isValid(s,startIndex,i)){
			s.insert(s.begin()+i+1,'.');//在符合的字符串后面加.
			pointNum++;
			backtracking(s,i+2,pointNum);
			s.erase(s.begin()+i+1);
			pointNum--;
		}else{
			continue;
		}
	}
}
//段位以0为开头的数字不合法
//段位里有非正整数字符不合法
//段位如果大于255了不合法
bool isValid(string& s,int begin,int end)
{
	if(begin>end){
		return false;
	}
	if(s[begin]=='0'&&begin!=end){
		return false;
	}
	int num = 0;
	for(int i = begin;i<=end;i++){
		//判断当前字符是否是 非正整数
		if(s[i]<'0'||s[i]>'9') {
			return false;
		}
		num = num*10 + s[i]-'0';
		if(num >255){//段位如果大于255了不合法
			return false;
		}
	}
	return true;
} 
vector<string> restoreIpAddresses(string s) {
	backtracking(s,0,0);
	return result;
}

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