Combination sum Ⅳ -- leetcode exercise

I haven't done a problem for a long time , More dishes 5555

Title Description

Here you are Different An array of integers nums , And a target integer target . Please start from nums Find and return the sum of target The number of element combinations of .

The data of the questions ensure that the answers are in line with 32 Bit integer range .

example

	 Input ：nums = [1,2,3], target = 4
	 Output ：7
	 explain ：
	 All possible combinations are ：
	(1, 1, 1, 1)
	(1, 1, 2)
	(1, 2, 1)
	(1, 3)
	(2, 1, 1)
	(2, 2)
	(3, 1)
	 Please note that , Different sequences are considered as different combinations .

Ideas

Be careful ： What the topic requires is that different order is also a combination

The easier way to think of is DFS, But the test timed out , I won't go into details here .

Dynamic programming

Create a length of target( The goal is )+1 Array of , Record each i（0<=i<=target） How many combinations of values of .

If the goal is 0, that dp[0]=1, Don't choose a number .

You can put nums Array sorting , Make two layers for loop , The outer layer is 1 ~ target, The inner layer is 0 ~ len(nums)-1.

dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+dp[i-nums[2]]+……+dp[i-nums[j]] (nums[j+1]>i)

Code

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        dp=[0]*(target+1)
        dp[0]=1
        for i in range(1,len(dp)):
            for j in range(len(nums)):
                if nums[j]>i:
                    break
                else:
                    dp[i]+=dp[i-nums[j]]
        return dp[-1]