Flame Chan494. Target Sum
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
Original Page
Even though the backtracking is useful here we can use dynamic programming to solve this problem to achieve less time complexity.
public int findTargetSumWays(int[] nums, int target) {
/**
sum(neg) + sum(pos) = sum(nums);
sum(pos) - sum(neg) = target;
sum(pos) = (sum(nums) + target) / 2
*/
int sum = Arrays.stream(nums).sum();
// that means the sum of the positive number is invalid, because the nums do not conclude float
if((sum+target)%2 != 0|| Math.abs(target) > sum){
return 0;
}
// here we find the summary of the positive numbers
int pos = (sum + target) >>1;
// dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods
int[][] dp = new int[nums.length+1][pos+1];
// if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
dp[0][0] = 1;
// if(nums[0] <= pos){
// dp[0][nums[0]] = 1;
// }
for(int i = 1; i <= nums.length; i++){
for(int j=0; j<=pos; j++){
if(nums[i-1] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
// Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
return dp[nums.length][pos];
}
