Count signs permutations to sum equal target #medium #dynamic_programming
Intuition
The DFS + memo: for every position and current target try plus sign and minus sign; terminal condition is target == 0; add memo using a HashMap or 2D array.
More interesting is how to do this bottom-up: for each new number nums[i], check if we have previous results in dp[i - 1][target] for every target in range -1000..1000, and if so, do a plus action and a minus action by adding it to dp[i][target-nums[i]] and dp[i][target+nums[i]].
The super-clever variant is a 1D dp (stealing it from others). It starts with math:
we are adding another number to the previous result
new_target + n = sum
new_target - n = target
2 * new_target = sum + target, or new_target = (sum + target) / 2.
That gives us the freedom to do just a plus operation, and reuse the same dp array, by adding the extra false-positive check: (sum + target) % 2 == 0, and abs(sum) >= abs(target).
Approach
let's implement all of the approaches to feel the numbers
Complexity
Time complexity: $$O(n^2)$$ to O(n)
Space complexity: $$O(n^2)$$ to O(n)
Code
fun findTargetSumWays(nums: IntArray, target: Int): Int {
val dp = HashMap<Pair<Int, Int>, Int>()
fun dfs(pos: Int, target: Int): Int = dp.getOrPut(pos to target) {
if (pos == nums.size) if (target == 0) 1 else 0
else dfs(pos + 1, target - nums[pos]) +
dfs(pos + 1, target + nums[pos])
}
return dfs(0, target)
}
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let mut dp = vec![vec![0; 2001]; nums.len()];
dp[0][1000 + nums[0] as usize] = 1; dp[0][1000 - nums[0] as usize] += 1;
for i in 1..dp.len() {
for target in 0..2001 {
if dp[i - 1][target] > 0 {
dp[i][target + nums[i] as usize] += dp[i - 1][target];
dp[i][target - nums[i] as usize] += dp[i - 1][target]
}
}
}; dp[dp.len() - 1][1000 + target as usize]
}
int findTargetSumWays(vector<int>& nums, int target) {
vector<int> dp(2001, 0); dp[0] = 1; int s = 0;
for (int n : nums) {
s += n;
for (int t = 1000 + target; t >= n; --t) dp[t] += dp[t - n];
}
return abs(s) < abs(target) || (s + target) % 2 > 0 ? 0: dp[(s + target) / 2];
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
