leetcode with 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.

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更:
最近在忙打工的一些事情,暂时停更一下,应该不会太久啦