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 num
class Solution { public int findTargetSumWays(int[] nums, int S) { if (nums == null || nums.length == 0) { return 0; } int sum = 0; for (int num: nums) { sum += num; } // unreachable sum if (S > sum || S < -sum) { return 0; } int[] arr = new int[2 * sum + 1]; arr[sum] = 1; for (int i = 0; i < nums.length; i++) { int[] curArr = new int[2 * sum + 1]; for (int j = 0; j < arr.length; j++) { if (arr[j] != 0) { // dp from center to both sides curArr[j - nums[i]] += arr[j]; curArr[j + nums[i]] += arr[j]; } } arr = curArr; } return arr[sum + S]; } }
原文：https://www.cnblogs.com/xuanlu/p/12216088.html