题目简介
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
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]
]
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
初见思路
- 区别只是在于下标i要包括
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = list()
combs = list()
candidates.sort()
def back_tracking(index) -> None:
if sum(combs) == target:
ans.append(combs[:])
return
for i in range(index,len(candidates)):
if sum(combs) > target:
break
combs.append(candidates[i])
back_tracking(i)
combs.pop()
back_tracking(0)
return ans
一种更好的减枝形式
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result =[]
candidates.sort()
self.backtracking(candidates, target, 0, [], result)
return result
def backtracking(self, candidates, target, startIndex, path, result):
if target == 0:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
if target - candidates[i] < 0:
break
path.append(candidates[i])
self.backtracking(candidates, target - candidates[i], i, path, result)
path.pop()
- 相比39增加去重的逻辑
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result =[]
candidates.sort()
self.backtracking(candidates, target, 0, [], result)
return result
def backtracking(self, candidates, target, startIndex, path, result):
if target == 0:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
if i > startIndex and candidates[i] == candidates[i-1]:
continue
if target - candidates[i] < 0:
break
path.append(candidates[i])
self.backtracking(candidates, target - candidates[i], i+1, path, result)
path.pop()
- 关键在于判断回文串和子串的拆分
class Solution:
def is_palindrome(self,s:str) -> bool:
return all([s[i] == s[len(s) - 1 - i] for i in range(len(s)//2)])
def back_track(self, s, start_index, path, result):
if start_index == len(s):
result.append(path[:])
return
for i in range(start_index + 1, len(s) + 1):
sub = s[start_index:i]
if self.is_palindrome(sub):
path.append(sub)
self.back_track(s, i, path, result)
path.pop()
def partition(self, s: str) -> List[List[str]]:
result = list()
self.back_track(s, 0, [], result)
return result
复盘思路
https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
