【代碼隨想錄訓練營】【Day 29】【回溯-3】| Leetcode 39， 41， 131

需強化知識點

startInex作用：一是處理是否可以有重復值，二是實現縱向遍歷（不能沒有）
去重要在數組有序的前提下進行
分割問題

題目

39. 組合總和

注意不要在for循環中亂用return，寫到終止條件上，for循環中應該用break

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:result = []def backtracking(candidates, target, start_index, path_sum, path, result):if path_sum > target:returnif path_sum == target:result.append(path[:])returnfor i in range(start_index, len(candidates)):path_sum += candidates[i]path.append(candidates[i])backtracking(candidates, target, i, path_sum, path, result)path.pop()path_sum -= candidates[i]candidates.sort()backtracking(candidates, target, 0, 0, [], result)        return result

40. 組合總和 II

去重：可以使用used數組，此處應該是同層不能取重復的數，used[i-1] == False，是會重復的情況
- 使用startIndex去重， i > startIndex，代表是在同層的情況，在進行橫向遍歷

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:def backtracking(result, path, target, total, candidates, startIndex):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:breakif i > startIndex and candidates[i] == candidates[i-1]:continuetotal += candidates[i]path.append(candidates[i])backtracking(result, path, target, total, candidates, i+1)total -= candidates[i]path.pop()result = []candidates.sort()backtracking(result, [], target, 0, candidates, 0)return result

131. 分割回文串

代碼隨想錄思路：遞歸用來縱向遍歷，for循環用來橫向遍歷，切割線（就是圖中的紅線）切割到字符串的結尾位置，說明找到了一個切割方法。
再次注意，for循環內不要亂用return（此處應該為continue），繼續下一種切割方案

class Solution:def partition(self, s: str) -> List[List[str]]:def isPalindrome(s):if len(s) == 1:return Trueleft, right = 0, len(s)-1while left < right:if s[left] != s[right]:return Falseleft += 1right -= 1return Truedef backtracking(s, path, result, startIndex):if startIndex == len(s):result.append(path[:])for i in range(startIndex, len(s)):select = s[startIndex:i+1]if not isPalindrome(select):continuepath.append(select)backtracking(s, path, result, i+1)path.pop()result = []backtracking(s, [], result, 0)return result