目录
详细布置:
1. 39. 组合总和
2. 40. 组合总和 II
3. 131. 分割回文串
详细布置:
1. 39. 组合总和
给你一个 无重复元素 的整数数组
candidates
和一个目标整数target
,找出candidates
中可以使数字和为目标数target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。对于给定的输入,保证和为
target
的不同组合数少于150
个。
建议:本题是 集合里元素可以用无数次,那么和组合问题的差别 其实仅在于 startIndex上的控制
本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下:
class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total > target:returnif total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):total += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i, path, result) # 不用i+1了,表示可以重复读取当前的数total -= candidates[i]path.pop()def combinationSum(self, candidates, target):result = []self.backtracking(candidates, target, 0, 0, [], result)return result
2. 40. 组合总和 II
给定一个候选人编号的集合
candidates
和一个目标数target
,找出candidates
中所有可以使数字和为target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。注意:解集不能包含重复的组合。
建议:本题开始涉及到一个问题了:去重。
注意题目中给我们 集合是有重复元素的,那么求出来的 组合有可能重复,但题目要求不能有重复组合。
本题的难点在于区别2中:集合(数组candidates)有重复元素,但还不能有重复的组合。
所以要在搜索的过程中就去掉重复组合。
所谓去重,其实就是使用过的元素不能重复选取。 这么一说好像很简单!
都知道组合问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了,我们是要同一树层上使用过,还是同一树枝上使用过呢?
回看一下题目,元素在同一个组合内是可以重复的,怎么重复都没事,但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重。
为了理解去重我们来举一个例子,candidates = [1, 1, 2], target = 3,(方便起见candidates已经排序了)
强调一下,树层去重的话,需要对数组排序!
class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if i > startIndex and candidates[i] == candidates[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i + 1, path, result)total -= candidates[i]path.pop()def combinationSum2(self, candidates, target):result = []candidates.sort()self.backtracking(candidates, target, 0, 0, [], result)return result
3. 131. 分割回文串
给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是回文串 。返回
s
所有可能的分割方案。
本题这涉及到两个关键问题:
- 切割问题,有不同的切割方式
- 判断回文
相信这里不同的切割方式可以搞懵很多同学了。
这种题目,想用for循环暴力解法,可能都不那么容易写出来,所以要换一种暴力的方式,就是回溯。
一些同学可能想不清楚 回溯究竟是如何切割字符串呢?
我们来分析一下切割,其实切割问题类似组合问题。
class Solution:def partition(self, s: str) -> List[List[str]]:'''递归用于纵向遍历for循环用于横向遍历当切割线迭代至字符串末尾,说明找到一种方法类似组合问题,为了不重复切割同一位置,需要start_index来做标记下一轮递归的起始位置(切割线)'''result = []self.backtracking(s, 0, [], result)return resultdef backtracking(self, s, start_index, path, result ):# Base Caseif start_index == len(s):result.append(path[:])return# 单层递归逻辑for i in range(start_index, len(s)):# 此次比其他组合题目多了一步判断:# 判断被截取的这一段子串([start_index, i])是否为回文串if self.is_palindrome(s, start_index, i):path.append(s[start_index:i+1])self.backtracking(s, i+1, path, result) # 递归纵向遍历:从下一处进行切割,判断其余是否仍为回文串path.pop() # 回溯def is_palindrome(self, s: str, start: int, end: int) -> bool:i: int = start j: int = endwhile i < j:if s[i] != s[j]:return Falsei += 1j -= 1return True