Target Sum
Target Sum: A Problem of Possibilities
Programming challenges often push us to think outside the box, and the Target Sum Problem is no exception. It presents an intriguing scenario that combines arithmetic operations with logical reasoning.
In this article, we’ll break down the problem, understand its constraints, and explore how to approach a solution effectively.
Problem Description
You are given an array of integers nums and an integer target.
For each number in the array, you can choose to either add or subtract it to a total sum.
- For example, if nums = [1, 2], one possible sum would be “+1-2=-1“.
If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: “+1-1” and “-1+1“.
Return the number of different ways that you can build the expression such that the total sum equals target.
Why Is This Problem Useful?
This problem is a great exercise for mastering:
- Dynamic Programming: Efficiently solving subproblems that require decision-making between choices.
- String Manipulation: Understanding how to handle character sequences and their relationships.
- Logical Thinking: Designing a solution while keeping track of multiple constraints.
Example 1
Input: nums = [2,2,2], target = 2
Output: 3
Explanation:
Explanation: There are 3 different ways to sum the input numbers to get a sum of 2.
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2
Constraints:
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- -1000 <= target <= 1000
Approaching the Solution
To solve the interleaving string problem, one might consider using a dynamic programming or recursive approach to evaluate all possible ways to combine the strings. The solution must ensure that all conditions for interleaving are satisfied at every step.
There are mainly Four approach to solve this problem –
- Recursion
- Dynamic Programming (Top-Down)
- Dynamic Programming (Bottom-up)
- Dynamic Programming (Space Optimized)
1.Recursion
- Time complexity: O(2^n)
- Space complexity: O(n)
Python
C++
Java
JavaScript
Python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def backtrack(i, total):
if i ==len(nums):
return total == target
return (backtrack(i + 1, total + nums[i]) +
backtrack(i + 1, total - nums[i]))
return backtrack(0, 0)C++
class Solution {
public:
int findTargetSumWays(vector& nums, int target) {
return backtrack(0, 0, nums, target);
}
int backtrack(int i, int total, vector& nums, int target) {
if (i == nums.size()) {
return total == target;
}
return backtrack(i + 1, total + nums[i], nums, target) +
backtrack(i + 1, total - nums[i], nums, target);
}
}; Java
public class Solution {
public int findTargetSumWays(int[] nums, int target) {
return backtrack(0, 0, nums, target);
}
private int backtrack(int i, int total, int[] nums, int target) {
if (i == nums.length) {
return total == target ? 1 : 0;
}
return backtrack(i + 1, total + nums[i], nums, target) +
backtrack(i + 1, total - nums[i], nums, target);
}
}JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
findTargetSumWays(nums, target) {
const backtrack = (i, total) => {
if (i === nums.length) {
return total === target ? 1 : 0;
}
return backtrack(i + 1, total + nums[i]) +
backtrack(i + 1, total - nums[i]);
}
return backtrack(0, 0);
}
}2. Dynamic Programming (Top-Down)
Time & Space Complexity
- Time complexity:
- Space complexity:
Python
Java
C++
JavaScript
Python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = {} # (index, total) -> # of ways
def backtrack(i, total):
if i == len(nums):
return 1 if total == target else 0
if (i, total) in dp:
return dp[(i, total)]
dp[(i, total)] = (backtrack(i + 1, total + nums[i]) +
backtrack(i + 1, total - nums[i]))
return dp[(i, total)]
return backtrack(0, 0)Java
public class Solution {
private int[][] dp;
private int totalSum;
public int findTargetSumWays(int[] nums, int target) {
totalSum = 0;
for (int num : nums) totalSum += num;
dp = new int[nums.length][2 * totalSum + 1];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < 2 * totalSum + 1; j++) {
dp[i][j] = Integer.MIN_VALUE;
}
}
return backtrack(0, 0, nums, target);
}
private int backtrack(int i, int total, int[] nums, int target) {
if (i == nums.length) {
return total == target ? 1 : 0;
}
if (dp[i][total + totalSum] != Integer.MIN_VALUE) {
return dp[i][total + totalSum];
}
dp[i][total + totalSum] = backtrack(i + 1, total + nums[i], nums, target) +
backtrack(i + 1, total - nums[i], nums, target);
return dp[i][total + totalSum];
}
}
C++
class Solution {
vector> dp;
int totalSum;
public:
int findTargetSumWays(vector& nums, int target) {
totalSum = accumulate(nums.begin(), nums.end(), 0);
dp = vector>(nums.size(), vector(2 * totalSum + 1, INT_MIN));
return backtrack(0, 0, nums, target);
}
int backtrack(int i, int total, vector& nums, int target) {
if (i == nums.size()) {
return total == target;
}
if (dp[i][total + totalSum] != INT_MIN) {
return dp[i][total + totalSum];
}
dp[i][total + totalSum] = backtrack(i + 1, total + nums[i], nums, target) +
backtrack(i + 1, total - nums[i], nums, target);
return dp[i][total + totalSum];
}
}; JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
findTargetSumWays(nums, target) {
const NEG_INF = Number.MIN_SAFE_INTEGER;
const totalSum = nums.reduce((a, b) => a + b, 0);
const dp = Array.from({ length: nums.length }, () =>
Array(2 * totalSum + 1).fill(NEG_INF));
const backtrack = (i, total) => {
if (i === nums.length) {
return total === target ? 1 : 0;
}
if (dp[i][total + totalSum] !== NEG_INF) {
return dp[i][total + totalSum];
}
dp[i][total + totalSum] = backtrack(i + 1, total + nums[i]) +
backtrack(i + 1, total - nums[i]);
return dp[i][total + totalSum];
}
return backtrack(0, 0);
}
}3. Dynamic Programming (Bottom-Up)
Time & Space Complexity
- Time complexity:
- Space complexity:
Python
Java
C++
JavaScript
Python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
dp = [defaultdict(int) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
for total, count in dp[i].items():
dp[i + 1][total + nums[i]] += count
dp[i + 1][total - nums[i]] += count
return dp[n][target]Java
public class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
Map[] dp = new HashMap[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = new HashMap<>();
}
dp[0].put(0, 1);
for (int i = 0; i < n; i++) {
for (Map.Entry entry : dp[i].entrySet()) {
int total = entry.getKey();
int count = entry.getValue();
dp[i + 1].put(total + nums[i],
dp[i + 1].getOrDefault(total + nums[i], 0) + count);
dp[i + 1].put(total - nums[i],
dp[i + 1].getOrDefault(total - nums[i], 0) + count);
}
}
return dp[n].getOrDefault(target, 0);
}
}
C++
class Solution {
public:
int findTargetSumWays(vector& nums, int target) {
int n = nums.size();
vector> dp(n + 1);
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (auto &p : dp[i]) {
dp[i + 1][p.first + nums[i]] += p.second;
dp[i + 1][p.first - nums[i]] += p.second;
}
}
return dp[n][target];
}
}; JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
findTargetSumWays(nums, target) {
const n = nums.length;
let dp = Array.from({ length: n + 1 }, () => ({}));
dp[0][0] = 1;
for (let i = 0; i < n; i++) {
for (let total in dp[i]) {
total = Number(total);
let count = dp[i][total];
dp[i + 1][total + nums[i]] = (dp[i + 1][total + nums[i]] || 0) + count;
dp[i + 1][total - nums[i]] = (dp[i + 1][total - nums[i]] || 0) + count;
}
}
return dp[n][target] || 0;
}
}4. Dynamic Programming (Space Optimized)
- Time complexity: O(n∗t)
- Space complexity: O(t)
Python
Java
C++
JavaScript
Python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = defaultdict(int)
dp[0] = 1
for num in nums:
next_dp = defaultdict(int)
for total, count in dp.items():
next_dp[total + num] += count
next_dp[total - num] += count
dp = next_dp
return dp[target]Java
public class Solution {
public int findTargetSumWays(int[] nums, int target) {
Map dp = new HashMap<>();
dp.put(0, 1);
for (int num : nums) {
Map nextDp = new HashMap<>();
for (Map.Entry entry : dp.entrySet()) {
int total = entry.getKey();
int count = entry.getValue();
nextDp.put(total + num,
nextDp.getOrDefault(total + num, 0) + count);
nextDp.put(total - num,
nextDp.getOrDefault(total - num, 0) + count);
}
dp = nextDp;
}
return dp.getOrDefault(target, 0);
}
} C++
class Solution {
public:
int findTargetSumWays(vector& nums, int target) {
unordered_map dp;
dp[0] = 1;
for (int num : nums) {
unordered_map nextDp;
for (auto& entry : dp) {
int total = entry.first;
int count = entry.second;
nextDp[total + num] += count;
nextDp[total - num] += count;
}
dp = nextDp;
}
return dp[target];
}
}; JavaScript
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
findTargetSumWays(nums, target) {
let dp = new Map();
dp.set(0, 1);
for (let num of nums) {
let nextDp = new Map();
for (let [total, count] of dp) {
nextDp.set((total + num),
(nextDp.get((total + num)) || 0) + count);
nextDp.set((total - num),
(nextDp.get((total - num)) || 0) + count);
}
dp = nextDp;
}
return dp.get(target) || 0;
}
}Conclusion
The Interleaving String problem is more than just a test of string manipulation skills; it’s a practical exercise in algorithmic thinking. It demonstrates the power of logical sequencing and helps build a strong foundation for solving real-world problems where multiple sequences or inputs need to be merged in specific ways.
By tackling problems like this, you sharpen your ability to think critically and design efficient solutions for complex challenges.
