不同路径过来的组合可能有重复。比如 [1,2,1] [1,1,2]
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
nums.sort()
dp=[0 for i in range(target+1)]
dp[0]=1
for i in range(target+1):
for value in nums:
if value>i:break
dp[i]+=dp[i-value]
return dp[target]
网友评论