Golang Li Kou leetcode 494. goals and

494. Objectives and

494. Objectives and

Answer key

subject ： Give an array , And a target, Array elements can be positive or negative , After the change sign , Sum of array elements =target Number of alternatives

Ideas ：1 Dynamic programming

 Set satisfaction target In the array , All positive sums are x, All negative sums are y
	x+y==target
	x+y+x-y=target+x-y
	 because x-y= All positive numbers minus all negative numbers = Array elements and , Set to sum
	2x=target+sum
	 therefore x=(sum - target) / 2
 Now the problem is to select several elements , Make the sum of the elements =x, Calculate the number of solutions 
 Then we can use dynamic programming to do 

dp[i][j]： before i Select from the elements , Make the sum of the elements equal to j  Number of alternatives 
 State shift ：dp[i][j] = dp[i-1][j]// No election    j < nums[i]
       dp[i][j] = dp[i-1][j] + dp[i-1][j-curVal]   Number of schemes = No election + choose  j>=nums[i]
 initial ：dp[0][0] = 1  before 0 Select and from the elements as 0 Number of alternatives  , You have to choose nothing ,1 Medium scheme 
 answer ：dp[n][neg]

2 violence dfs, Enumerate all the situations

func findTargetSumWays(nums []int, target int) int {
    
	ans := 0
	var dfs func(idx int, cur int)
	dfs = func(idx int, cur int) {
    
		if idx == len(nums) {
    
			if cur == target {
    
				ans++
			}
			return
		}
		dfs(idx+1, cur+nums[idx])
		dfs(idx+1, cur-nums[idx])
	}
	dfs(0, 0)
	return ans
}

Code

func findTargetSumWays(nums []int, target int) int {
    
	sum, n := 0, len(nums)
	for _, v := range nums {
    
		sum += v
	}
	if sum < target || (target+sum)%2 != 0 {
    
		return 0
	}
	neg := (sum - target) / 2
	dp := make([][]int, n+1)
	for i := range dp {
    
		dp[i] = make([]int, neg+1)
	}
	dp[0][0] = 1
	for i := 1; i <= n; i++ {
    
		for j := 0; j <= neg; j++ {
    
			curVal := nums[i-1]
			if j < curVal {
    
				dp[i][j] = dp[i-1][j] // No election 
			} else {
    
				dp[i][j] = dp[i-1][j] + dp[i-1][j-curVal] // Number of schemes = Unselected number + Number of options selected 
			}
		}
	}
	return dp[n][neg]
}