Problem
Given an integer array nums and an integer target, return the number of different expressions that can be created by adding either+ or - before each number such that the resulting sum equals target.
Each number must be used exactly once.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,1,1,1,1]
target = 3Output
5Solution
This solution uses Backtracking to explore both possible choices for every number: add it to the current sum or subtract it from the current sum.
When all numbers have been processed, the current sum is compared with the target. If they are equal, one valid expression has been found and the count is increased.
After both recursive branches are explored, the recursion returns to the previous state and continues with the next possible choice.
class Solution {
public int findTargetSumWays(int[] nums, int target) {
return backtrack(nums, 0, target);
}
private int backtrack(int[] nums, int index, int target) {
// All numbers have been assigned a sign.
if (index == nums.length) {
return target == 0 ? 1 : 0;
}
// Choose '+' for the current number.
int add = backtrack(
nums,
index + 1,
target + nums[index]
);
// Choose '-' for the current number.
int subtract = backtrack(
nums,
index + 1,
target - nums[index]
);
// Count valid expressions from both choices.
return add + subtract;
}
}
Complexity
For every number, the algorithm makes two choices: + or -. Therefore, there are2n possible expressions, giving a time complexity of O(2n).
The recursion depth is
O(n), so the auxiliary space complexity is O(n).