算法练习Day22 （Leetcode/Python-回溯算法）

39. Combination Sum

Given an array of?distinct?integers?candidates?and a target integer?target, return?a list of all?unique combinations?of?candidates?where the chosen numbers sum to?target.?You may return the combinations in?any order.

The?same?number may be chosen from?candidates?an?unlimited number of times. Two combinations are unique if the?

frequency

?of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to?target?is less than?150?combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

思路：从无元素重复的candidates中找和为target的组合，每一个组合中candidates中的元素可以被多次重复选取。

这道题和昨天的非常类似，只不过昨天的不能重复选取。

在今天这道题中，

1. 允许重复选择同一数字：递归调用 self.backtracking 时传入的 startIndex 是 i 而不是 i+1。这意味着在每一层递归中，都可以重新选择当前正在考虑的数字。例如，如果 candidates[i] 是一个有效的选择，它可以在同一路径中多次被选择。（昨天那道题目里，元素不能被重复选取，所以传入的startIndex 是i+1）

2. 避免重复的组合：即使一个数字可以被多次选择，通过从 startIndex 开始循环，算法仍然确保了不会生成重复的组合。这是因为在每一层递归中，只考虑 startIndex 之后的元素（包括 startIndex 本身），这意味着你不会在后续的递归中重新考虑之前已经处理过的元素。例如，如果组合 [2, 3] 已经被考虑过，那么在后续的递归中就不会再生成 [3, 2] 这样的组合，因为当处理到数字 3 时，递归不会回溯到数字 2。

solution:

class Solution(object):
    def backtracking(self, candidates,target,cur_sum,path,startIndex,result):
        if cur_sum == target:
            result.append(path[:])
            return # 别忘记这个return！！
        if cur_sum > target:
            return 
        for i in range(startIndex, len(candidates)):# 因为这里给的candiates是没有重复的，所以才可以这样遍历子节点而不用担心生成的path会重复。
            cur_sum += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates,target,cur_sum,path,i,result)
            path.pop()
            cur_sum -= candidates[i]

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = [] 
        self.backtracking(candidates,target,cur_sum=0,path=[],startIndex=0,result=result)
        return result