題目簡介

39. 組合總和
給你一個(gè) 無重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個(gè) 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同，則兩種組合是不同的。

對于給定的輸入，保證和為 target 的不同組合數(shù)少于 150 個(gè)。

40. 組合總和 II
給定一個(gè)候選人編號的集合 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用 一次 。

注意：解集不能包含重復(fù)的組合。

示例 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. 分割回文串
給你一個(gè)字符串 s，請你將 s 分割成一些子串，使每個(gè)子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正著讀和反著讀都一樣的字符串。

示例 1：

輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]
示例 2：

輸入：s = "a"
輸出：[["a"]]

初見思路

39. 區(qū)別只是在于下標(biāo)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()

40. 相比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()

131. 關(guān)鍵在于判斷回文串和子串的拆分

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

復(fù)盤思路

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

重點(diǎn)難點(diǎn)

今日收獲