目录39. 组合总和题目描述解题思路40. 组合总和 II题目描述解题思路没太理解明天看131. 分割回文串题目描述解题思路脑袋不太清晰39. 组合总和题目描述给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。解题思路做本题的时候通过三个思考过程思考一输出不同的排列16.png原因没有对start做限制每一层的遍历都是2367以至于2-2-32-3-2实际是一个答案遍历如下以2为根节点示例18.jpg思考二限制的太死17.png原因将此题的解法同昨天组合类似start是用start1来进行递归这样不会使用自己的节点即如图19.jpg思考三我又模拟了一下目标示例计算如下20.jpg想要不出现思考一中的重复因为2-2-3出现过所以在这个过程中不应该出现2-3-2基于以上思考我画出这样的遍历过程上述三个思考过程最大的区别就是start的取值针对思考三写出各个过程的start发现都是都是数组的当前元素的下标iclass Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: self.res [] self.backtracking(0,target,[],candidates,0) return self.res def backtracking(self,total,target,path,candidates,start): if total target: self.res.append(path[:]) return if total target: return for i in range(start,len(candidates)): path.append(candidates[i]) self.backtracking(totalcandidates[i],target,path,candidates,i) path.pop()40. 组合总和 II题目描述给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。注意解集不能包含重复的组合。解题思路没太理解明天看class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: self.res [] self.used [False] * len(candidates) candidates.sort() self.backtracking(candidates,target,[],0,0) return self.res def backtracking(self,candidates,target,path,total,start): if total target: return if total target: self.res.append(path[:]) return for i in range(start,len(candidates)): #去重 if i 0 and candidates[i] candidates[i - 1] and self.used[i-1] False: continue path.append(candidates[i]) self.used[i] True self.backtracking(candidates,target,path,totalcandidates[i],i1) self.used[i] False path.pop()131. 分割回文串题目描述给你一个字符串s请你将s分割成一些 子串使每个子串都是回文串。返回s所有可能的分割方案。解题思路脑袋不太清晰由题可知把一个字符串切成若干段每一段必须是回文且所有合法切法举个栗子字符串缝隙a|a|b有2个可切割位置要枚举所有合法切法start表示下一次从哪个下标开始切同上循环中截取s[start:i1]这一段判断这段是否为回文是就放入path往后切不是就跳过当start len(s)说明切完了模拟一下这个过程21.jpgclass Solution: def partition(self, s: str) - List[List[str]]: self.path [] self.res [] self.backtracking(s,0) return self.res def backtracking(self,s, start): if start len(s): self.res.append(self.path[:]) return for i in range(start,len(s)): if self.is_huiwen(s,start,i): self.path.append(s[start:i1]) self.backtracking(s,i1) self.path.pop() def is_huiwen(self,s,start,end): i,j start,end while i j: if s[i] !s[j]: return False i 1 j - 1 return True