代码随想录算法训练营第二十七天| 39.组合总和、40.组合总和II、131.分割回文串
题目
39.组合总和
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
class Solution:def __init__(self):self.res = []def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.backtracking(0, 150, target, candidates, [])return self.resdef backtracking(self, starIndex, k, target, candidates, curPath):if sum(curPath) > target:returnif sum(curPath) == target:self.res.append(curPath[:])return for i in range(starIndex, len(candidates)):curPath.append(candidates[i])self.backtracking(i, k, target, candidates, curPath)curPath.pop()
题目
40.组合总和II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
**注意：**解集不能包含重复的组合。
class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:res = []candidates.sort()self.backtracking(candidates, 0, target, [], res)return resdef backtracking(self, candidates, curIndex, target, curPath, res):if sum(curPath) == target:res.append(curPath[:])returnfor i in range(curIndex, len(candidates)):if sum(curPath) > target:breakif i > curIndex and candidates[i] == candidates[i-1]:continuecurPath.append(candidates[i])self.backtracking(candidates, i+1, target, curPath, res)curPath.pop()
题目
131.分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
class Solution:def partition(self, s: str) -> List[List[str]]:res = []self.backstracking(s, 0, [], res)return resdef backstracking(self, s, starIndex, curPath, res):if starIndex == len(s):res.append(curPath[:])returnfor i in range(starIndex, len(s)):if self.isValid(s, starIndex, i):curPath.append(s[starIndex: i+1])self.backstracking(s, i+1, curPath, res)curPath.pop()def isValid(self, curPath, starIndex, endIndex):low, high = starIndex, endIndexwhile low < high:if curPath[low] != curPath[high]:return Falselow += 1high -= 1return True
