当前位置：网站首页>Brainstorm: Goals and

Brainstorm: Goals and

2022-08-10 15:25:00 【InfoQ】

title

Given an array of non-negative integers, a1, a2, ..., an, and a target number, S.Now you have two symbols + and -.For any integer in the array, you can choose a sign from + or - to prepend.

Returns the number of methods that can make the final array and all the symbols added to the target number S.

Example:

Input: nums: [1, 1, 1, 1, 1], S: 3
Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1= 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to make the final goal sum to 3.

Tips:

The array is not empty and the length will not exceed 20.

The initial array sum will not exceed 1000.

The final result returned is guaranteed to be stored as a 32-bit integer.

Solution ideas

Assuming that the sum of addition is x, then the sum corresponding to subtraction is sum - x.So what we require is x - (sum - x) = S, which can be deduced: x = (S + sum) / 2.

Therefore, this problem can be transformed into, filling capacity x knapsack, there are several ways.

If (S + sum) / 2 is not an integer, there is no solution at this time; and if the target number S is greater than sum, there is also no solution at this time.

This problem needs to be solved by filling the backpack. There are several methods in total, which is a combination problem.

The first step is to determine the dp array and the meaning of the subscript: p[j] means: there are dp[j] methods to fill up a bag with such a large volume of j.

The second step is to determine the recursion formula: the formula for finding a combination problem is generally dp[j] += dp[j - nums[i]].

The third step, dp array initialization: dp[0] must be initialized to 1 during initialization, because dp[0] is the origin of all recursive results in the formula, dp[0]0] = 1, which is also well explained in theory. There is one way to fill a backpack with a capacity of 0, which is to load 0 items.

The fourth step is to determine the traversal order: For the one-dimensional dp traversal of the 01 knapsack problem, nums is placed in the outer loop, target is in the inner loop, and the inner loop is in reverse order.

Code Implementation

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 int sum = 0;
 for(int i = 0; i < nums.length; i++) sum += nums[i];
 if ((target + sum) % 2 != 0) return 0;
 int size = (target + sum) / 2;
 if(size < 0) size = -size;
 int[] dp = new int[size + 1];
 dp[0] = 1;
 for (int i = 0; i < nums.length; i++) {
 for (int j=size; j >= nums[i]; j--) {
 dp[j] += dp[j - nums[i]];
 }
 }
 return dp[size];
 }
}