494. Target Sum

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”.

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

Code

688

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        
        if(target < -sum || target > sum) return 0;
        
        int[] dp = new int[2 * sum + 1];
        
        dp[nums[0] + sum] = 1;
        // [0,0,0,0,0,0,0,0,1]
        dp[-nums[0] + sum] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2 * sum + 1];
            
            for (int s = 0; s <= 2 * sum; s++) {              
                if (dp[s] > 0) {
                    next[s + nums[i]] += dp[s];
                    next[s - nums[i]] += dp[s];
                }
            }
            
            dp = next;
        }
        
        return dp[target + sum];
    }
}

class Solution {
    int res = 0;

    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, 0, target, 0);
        return res;
    }

     private void dfs(int[] nums, int start, int target, int curr){
        if(start == nums.length){
            if (target == curr) res++;
            return;
        }

        dfs(nums, start + 1, target, curr + nums[start]);
        dfs(nums, start + 1, target, curr - nums[start]);
    }
}