題目:

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.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

給定幾個可以使用的數(candidates),再給定一個目標值(target)
candidates為排序過的陣列
找出用candidates的值相加(可重複使用),等於target的所有可能組合

我用遞迴(backtrack)來實作這題

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans=[]
        temp=[]
        
        def backtrack(s,start):
            if s==target:
                ans.append(temp[:])
                return
                
            if s>target:
                return
            
            for i in range(start,len(candidates)):
                temp.append(candidates[i])
                backtrack(s+candidates[i],i)
                temp.pop()
                
        backtrack(0,0)
        
        return ans

先設置陣列ans來存放,和陣列temp來探索可能
函式backtrack需要兩個參數
s表示現在值加到哪了,start表示上次用到哪個candidates值

若s等於target,則將temp目前記錄的組合放入ans中

若s大於target,則直接回傳,放棄此組合後面的可能

若s小於target,繼續往下探索可能
從start位置開始的candidates一個一個往下遞迴
這樣探索的所有組合都是排序過的(candidates是排序陣列)
不會出現填入重複組合的問題

先將該candidates放入temp
再往下backtrack(s+該值,該值位置)
backtrack結束表示此組合後的可能都被探索過了
將該candidates從temp移除

執行backtrack(0,0)後回傳ans即可
最後執行時間82ms(faster than 90.39%)

我在討論區有看到dp解如下

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target+1)]
        for c in candidates:                                 
            for i in range(c, target+1):                      
                if i == c: 
                    dp[i].append([c])
                for comb in dp[i-c]: 
                    dp[i].append(comb + [c])
        return dp[-1]

建立陣列dp,每項存放用candidates值組合出index值的組合
所以dp共有target+1項(組合出0~target的組合)

對每一個candidates(c),在c~target的範圍(i)
若i為c,則在dp[i]放入[c]這個可能

同時在dp[i-c]的所有陣列+[c]後放入dp[i]
因為target=i-c的所有組合再放入一個c,皆為target=i的可能

執行完後回傳dp最後一項,即dp[target]
最後執行時間53ms(faster than 99.54%)

那我們下題見

8/14更:
最近在忙打工的一些事情,暫時停更一下,應該不會太久啦