今天是紀錄LeetCode解題的第三十九天

第三十九題題目：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.

給定一個包含不同整數的數組和目標整數target，回傳所有滿足所選數字總和為target的串列組合，可以按任意順序回傳，同一個數字可以被無限次選中，如果兩個組合中至少有一個頻率不同，這兩個組合是唯一的

產生的測試案例使得對於給定的輸入，總和等於target的唯一組合數量少於 150 個組合

解題思路

遍歷整個canditates，把遍歷到的數字加到path裡，判斷總和total==target表示找到組合，把path存進result裡之後回溯找其他組合，如果total > target就馬上回溯(繼續遍歷下去沒意義)。
注意這裡我們要遍歷的範圍是for i in range(start,len(candidates))，第一次執行時start是0(i=0)，而每一次遞迴時都是傳遞i，也就是說下一次的遞迴start = i(因為同個數字可以重複使用，例如範例1一開始i=0時選擇數字2，下一次遞迴時傳遞i=0，start=0，所以又再一次選擇了數字2)，特別提這點因為第四十題在這個部分會有所不同

程式碼

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        def backtracking(start,path,total):
            if total == target:
                result.append(path[:])
                return
            if total > target:
                return
            for i in range(start,len(candidates)):
                path.append(candidates[i])
                backtracking(i,path,total + candidates[i])
                path.pop()

        backtracking(0,[],0)
        return result

執行過程(candidates = [2,3,6,7], target = 7)

回溯的過程大概如上，執行完全部就會得到答案result = [[2,2,3],[7]]