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.
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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
int[] signs = new int[n];
Arrays.fill(signs, -1);
return solve(signs, nums, target, n, 0);
}
private int solve(int[] signs, int[] nums, int target, int n, int idx) {
int ct = 0;
for (int i = idx; i < n; i++) {
signs[i] = 1;
ct += solve(signs, nums, target, n, i + 1);
signs[i] = -1;
}
for (int i = 0; i < n; i++)
target -= nums[i] * signs[i];
return target == 0 ? ++ct : ct;
}
}class Solution {
int[] nums;
int target, n, range;
public int findTargetSumWays(int[] nums, int target) {
this.nums = nums;
this.target = target;
this.n = nums.length;
range = Arrays.stream(nums).sum();
int[][] dp = new int[n][2 * range + 1];
for (int[] r: dp)
Arrays.fill(r, -1);
return solve(0, 0, dp);
}
private int solve(int idx, int total, int[][] dp) {
if (idx == n)
return total == target ? 1 : 0;
if (dp[idx][total + range] != -1)
return dp[idx][total + range];
return dp[idx][total + range] = solve(idx + 1, total + nums[idx], dp) + solve(idx + 1, total - nums[idx], dp);
}
}class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
int[] signs = new int[n];
Arrays.fill(signs, -1);
return solve(signs, nums, target, n, 0);
}
private int solve(int[] signs, int[] nums, int target, int n, int idx) {
int ct = 0;
for (int i = idx; i < n; i++) {
signs[i] = 1;
ct += solve(signs, nums, target, n, i + 1);
signs[i] = -1;
}
for (int i = 0; i < n; i++)
target -= nums[i] * signs[i];
return target == 0 ? ++ct : ct;
}
}