代码随想录算法训练营Day27|leetcode39 组合总和、leetcode40 组合总和II、leetcode131.分割回文串

 leetcode39 组合总和

思路：本题要注意start_index依旧需要，但是在循环时不需要加一，因为结果是可以重复的，另外要注意在结束条件中需要加上当sum>target时也需要返回。

class Solution:
    def backtracking(self, candidates, target, start_index, sum, results, path):
        if sum > target:
            return
        if sum == target:
            results.append(path[:])

        for i in range(start_index, len(candidates)):
            path.append(candidates[i])
            sum += candidates[i]
            self.backtracking(candidates, target, i, sum, results, path)
            sum -= candidates[i]
            path.pop()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        self.backtracking(candidates, target, 0, 0, results, [])
        return results

 leetcode40 组合总和II

思路：本题与前一题最主要的区别是本题需要做一个去重的操作，去重的思路是先把数组排序，递归时如果当前值等于前一个值就不从这个值开始递归，因为会重复，其他地方与上一题基本相同。

class Solution:
    def backtracking(self, candidates, target, start_index, sum, results, path):
        if sum > target:
            return
        if sum == target:
            results.append(path[:])

        for i in range(start_index, len(candidates)):           #去重
            if i > start_index and candidates[i] == candidates[i - 1]:
                continue                                      #注意这里用continue而不是return
 
            path.append(candidates[i])
            sum += candidates[i]
            self.backtracking(candidates, target, i + 1, sum, results, path)
            sum -= candidates[i]
            path.pop()

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, results, [])
        return results

 leetcode131.分割回文串

 思路：没听懂。