代码随想录算法训练营 Day 20

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        def backtracking(s, arr, start):
            if s > target:
                return
            if s == target:
                res.append(arr[:])
                return
            
            # 从开始索引向后遍历，保证了结果不会重复
            for i in range(start, len(candidates)):
                s += candidates[i]
                arr.append(candidates[i])
                backtracking(s, arr, i)
                s -= candidates[i]
                arr.pop()
        
        backtracking(0, [], 0)

        return res

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def backtracking(start, arr, s):
            if s > target:
                return
            if s == target:
                res.append(arr[:])
                return
            
            for i in range(start, len(candidates)):
                # 排序后数组如果当前元素和之前相同，可以直接跳过
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                s += candidates[i]
                arr.append(candidates[i])
                backtracking(i + 1, arr, s)
                s -= candidates[i]
                arr.pop()
        
        backtracking(0, [], 0)

        return res

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        def backtracking(start, s, arr):
            if start == len(s):
                res.append(arr[:])
            
            for i in range(start, len(s)):
                substring = s[start:i + 1]
                if substring == substring[::-1]:
                    arr.append(substring)
                    backtracking(i + 1, s, arr)
                    arr.pop()
        
        backtracking(0, s, [])

        return res

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 创建二维dp数组，表示dp[i][j]代表从i到j的子串是否为回文
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    # 两种子串为回文的情况: 1.长度为2；2.除开这两个字符剩下的也是回文
                    if length == 2 or dp[i + 1][j - 1]:
                        dp[i][j] = 1

        res = []
        def backtracking(start, s, arr):
            if start == len(s):
                res.append(arr[:])
            
            for i in range(start, len(s)):
                if dp[start][i]:
                    arr.append(s[start:i+1])
                    backtracking(i + 1, s, arr)
                    arr.pop()
        
        backtracking(0, s, [])

        return res