Give you an array of different integers, nums, and a target integer, target. Find and return the number of combinations of elements from nums that add up to target.

The question data ensures that the answers fit into the 32-bit integer range.

Example 1:

Input: nums = [1,2,3], target = 4 output: 7 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3), (2, 1, 1) (2, 2) (3, 1) please note that in a different order of sequence is regarded as different combinations. Example 2:

Input: nums = [9], target = 3 Output: 0

Tip:

1 <= nums.length <= 200 1 <= nums[I] <= 1000 All elements in NUMS are different 1 <= target <= 1000

Their thinking

An array of meaning

Enumerates the values from 1 to target, using a one-dimensional array to record the number of combinations that can make up the current element

The state transition equation is going to be

		for _, num := range nums {// Enumerate nums arrays
			if i-num>0&&dp[i-num]>0{
				dp[i]+=dp[i-num]
			}
		}
Copy the code

Dp [i-num] = dp[i-num] = dp[i-num] = dp[i-num] = dp[i-num]

Initialize the

	for _, num := range nums {
        if num>target {
          continue  
        }
		dp[num]=1
	}
Copy the code

Nums =1; dp[num]=1

code

func combinationSum4(nums []int, target int) int {

	dp := make([]int, target+1)
   
	for _, num := range nums {
        if num>target {
          continue  
        }
		dp[num]=1
	}
	for i := 1; i <=target; i++ {
		for _, num := range nums {
			if i-num>0&&dp[i-num]>0{
				dp[i]+=dp[i-num]
			}
		}
	}
	return dp[target]

}
Copy the code