Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and -as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 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 assign symbols to make the sum of nums be target 3.
因为这里涉及到多种不同的选择，所以很容易联想到用dfs，代码如下：

 class Solution {

     public int findTargetSumWays(int[] nums, int S) {

         int[] count = {  };

         helper(nums, , S, count);

         return count[];

     }

     private void helper(int[] nums, int index, int S, int[] count) {

         if (index == nums.length && S == ) {

             count[]++;

         }

         if (index >= nums.length) return;

         helper(nums, index + , S + nums[index], count);

         helper(nums, index + , S - nums[index], count);

     }

 }

但是这种方法明显是没有优化的，所以时间比其他方法要高。简单的优化就是当我们到了i-th这个位置的时候，如果发现后面部分的值的和或者差都不可能达到target值，我们就应该放弃。

 public class Solution {

     public int findTargetSumWays(int[] nums, int S) {

         if(nums == null || nums.length == ) return ;

         int n = nums.length;

         int[] sums = new int[n];

         int[] count = {  };

         sums[n - ] = nums[n - ];

         for (int i = n - ; i >= ; i--) {

             sums[i] = sums[i + ] + nums[i];

         }

         helper(nums, sums, S, , count);

         return count[];

     }

     public void helper(int[] nums, int[] sums, int target, int pos, int[] count){

         if(pos == nums.length && target == ){

             count[]++;

         }

         if (pos == nums.length) return;

         if (sums[pos] < Math.abs(target)) return;

         helper(nums, sums, target + nums[pos], pos + , count);

         helper(nums, sums, target - nums[pos], pos + , count);

     }

 }

还有就是通过dp来做，解法如下：https://leetcode.com/problems/target-sum/discuss/97335/Short-Java-DP-Solution-with-Explanation

this is a classic knapsack problem
in knapsack, we decide whether we choose this element or not
in this question, we decide whether we add this element or minus it

So start with a two dimensional array dp[i][j] which means the number of ways for first i-th element to reach a sum j

we can easily observe that dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i],

Another part which is quite confusing is return value, here we return dp[sum+S], why is that?

because dp's range starts from -sum --> 0 --> +sum
so we need to add sum first, then the total starts from 0, then we add S

Actually most of Sum problems can be treated as knapsack problem, hope it helps

 public int findTargetSumWays(int[] nums, int S) {

       int sum = ;

       for(int n: nums){

         sum += n;

       }

       if (S < -sum || S > sum) { return ;}

       int[][] dp = new int[nums.length + ][  * sum + ];

       dp[][ + sum] = ; // 0 + sum means 0, 0 means -sum,  check below graph

       for(int i = ; i <= nums.length; i++){

         for(int j = ; j <  * sum + ; j++){

           if(j + nums[i - ] <   * sum + ) dp[i][j] += dp[i - ][j + nums[i - ]];

           if(j - nums[i - ] >= ) dp[i][j] += dp[i - ][j - nums[i - ]];

         }

       }

       return dp[nums.length][sum + S];

     }

巴特西

Target Sum

最新文章

热门文章