medium
相关题: http://rainykat.blogspot.com/2017/01/leetcodegf-282-expression-add.html
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.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
Complexity: O(2^n)
public class Solution { public int findTargetSumWays(int[] nums, int S) { if(nums == null)return 0; return dfs(nums, S, 0, 0); } public int dfs(int[] nums, int S, int index, int sum){ int res = 0; if(index == nums.length){ if(sum == S) res++; return res; } res += dfs(nums, S, index + 1, sum + nums[index]); res += dfs(nums, S, index + 1, sum - nums[index]); return res; } }
Optimization: If the sum of all elements left is smaller than absolute value of target, there will be no answer following the current path. Thus we can return.
public class Solution { public int findTargetSumWays(int[] nums, int S) { if(nums == null)return 0; int n = nums.length; int[] sums = new int[n]; sums[n-1] = nums[n-1]; for(int i = n-2; i >= 0; i--){ sums[i] = nums[i] + sums[i+1]; } return dfs(nums, sums, S, 0, 0); } public int dfs(int[] nums, int[] sums, int S, int index, int sum){ int res = 0; if(index == nums.length){ if(sum == S) res++; return res; } if(sums[index] < Math.abs(S - sum))return 0; res += dfs(nums, sums, S, index + 1, sum + nums[index]); res += dfs(nums, sums, S, index + 1, sum - nums[index]); return res; } }
No comments:
Post a Comment