Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonFacebook

Target Sum

Choose your preparation mode4 modes available
🎯
Target Sum
mediumDPAmazonFacebook

Imagine you have a list of numbers and want to assign '+' or '-' signs to each so that the total equals a target sum. How many ways can you do this?

💡 This problem is a classic example of how a seemingly simple combinatorial problem can be transformed into a subset sum counting problem. Beginners often struggle because the problem asks for counting ways with signs, which is not straightforward. Understanding the problem as a variation of the 0/1 knapsack pattern helps unlock efficient solutions.
📋
Problem Statement

Given an array of integers nums and an integer target, return the number of different expressions that can be built by adding '+' or '-' before each integer such that the resulting expression evaluates to target. Input: nums (list of integers), target (integer) Output: integer representing the count of valid expressions.

1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 10000 ≤ sum(nums[i]) ≤ 1000-1000 ≤ target ≤ 1000
💡
Example
Input"nums = [1,1,1,1,1], target = 3"
Output5

There are 5 ways to assign signs to get sum 3: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.

  • nums = [0,0,0,0,0], target = 0 → 32 (all combinations of + and - count)
  • nums = [1000], target = 1000 → 1 (only +1000 works)
  • nums = [1], target = 2 → 0 (no way to reach 2)
  • nums = [], target = 0 → 1 (empty expression counts as one way)
🔁
Why DP?
Why greedy fails:

Greedy fails because choosing '+' or '-' for each number independently without considering future choices can miss valid combinations. For example, with nums=[1,2,3], target=0, greedily assigning '+' to all yields 6, not 0. The problem requires exploring all sign assignments.

DP state:

dp[i][sum] represents the number of ways to assign signs to the first i numbers to achieve a sum equal to 'sum'.

Recurrence:dp[i][sum] = dp[i-1][sum - nums[i-1]] + dp[i-1][sum + nums[i-1]]

The number of ways to reach 'sum' at index i is the sum of ways to reach 'sum - current number' and 'sum + current number' at the previous index.

⚠️
Common Mistakes
Not handling zero values correctly

Undercounts ways because zero can be added or subtracted without changing sum, doubling counts

✅ Ensure dp updates account for zeros by adding counts properly

Not offsetting sums to handle negative indices

Array index out of bounds or incorrect results due to negative indexing

✅ Use offset equal to total sum to shift sums to non-negative indices

Using forward iteration in 1D dp causing double counting

Incorrect counts because updated states are reused in same iteration

✅ Iterate sums backwards when updating 1D dp array

Not checking target range before accessing dp

Index out of range errors or wrong answers when target is outside possible sum range

✅ Return 0 if target < -total or target > total before dp lookup

🧠
Brute Force (Pure Recursion)
💡 Starting with brute force helps understand the problem's combinatorial nature and why naive recursion is inefficient due to repeated calculations.

Intuition

Try all combinations of '+' and '-' for each number recursively and count how many expressions evaluate to the target.

Algorithm

  1. Define a recursive function that takes current index and current sum.
  2. If index equals length of nums, check if current sum equals target; if yes, return 1 else 0.
  3. Recursively call the function twice: once adding current number, once subtracting it.
  4. Sum the results of both recursive calls and return.
💡 The recursion tree grows exponentially because each number doubles the number of expressions to check.
Recurrence:f(i, sum) = f(i+1, sum + nums[i]) + f(i+1, sum - nums[i])
</>
Code
def findTargetSumWays(nums, target):
    def backtrack(i, current_sum):
        if i == len(nums):
            return 1 if current_sum == target else 0
        return backtrack(i+1, current_sum + nums[i]) + backtrack(i+1, current_sum - nums[i])

    return backtrack(0, 0)

# Example usage
if __name__ == '__main__':
    print(findTargetSumWays([1,1,1,1,1], 3))  # Output: 5
Line Notes
def backtrack(i, current_sum):Defines recursive helper to explore sign assignments
if i == len(nums):Base case: all numbers processed
return 1 if current_sum == target else 0Count 1 if sum matches target, else 0
return backtrack(i+1, current_sum + nums[i]) + backtrack(i+1, current_sum - nums[i])Explore both '+' and '-' choices
public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return backtrack(nums, target, 0, 0);
    }

    private int backtrack(int[] nums, int target, int index, int currentSum) {
        if (index == nums.length) {
            return currentSum == target ? 1 : 0;
        }
        return backtrack(nums, target, index + 1, currentSum + nums[index]) +
               backtrack(nums, target, index + 1, currentSum - nums[index]);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findTargetSumWays(new int[]{1,1,1,1,1}, 3)); // 5
    }
}
Line Notes
public int findTargetSumWays(int[] nums, int target)Entry point calling recursive helper
if (index == nums.length)Base case: all elements processed
return currentSum == target ? 1 : 0;Return 1 if target reached, else 0
return backtrack(...) + backtrack(...)Sum ways from '+' and '-' choices
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return backtrack(nums, target, 0, 0);
    }

private:
    int backtrack(vector<int>& nums, int target, int index, int currentSum) {
        if (index == nums.size()) {
            return currentSum == target ? 1 : 0;
        }
        return backtrack(nums, target, index + 1, currentSum + nums[index]) +
               backtrack(nums, target, index + 1, currentSum - nums[index]);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,1,1,1,1};
    cout << sol.findTargetSumWays(nums, 3) << endl; // 5
    return 0;
}
Line Notes
int backtrack(vector<int>& nums, int target, int index, int currentSum)Recursive helper exploring sign assignments
if (index == nums.size())Base case: all numbers processed
return currentSum == target ? 1 : 0;Count 1 if sum matches target
return backtrack(...) + backtrack(...)Sum ways from '+' and '-' choices
function findTargetSumWays(nums, target) {
    function backtrack(i, currentSum) {
        if (i === nums.length) {
            return currentSum === target ? 1 : 0;
        }
        return backtrack(i + 1, currentSum + nums[i]) + backtrack(i + 1, currentSum - nums[i]);
    }
    return backtrack(0, 0);
}

// Example usage
console.log(findTargetSumWays([1,1,1,1,1], 3)); // 5
Line Notes
function backtrack(i, currentSum)Recursive helper to explore all sign assignments
if (i === nums.length)Base case: all elements processed
return currentSum === target ? 1 : 0;Count 1 if sum matches target
return backtrack(i + 1, currentSum + nums[i]) + backtrack(i + 1, currentSum - nums[i])Explore both '+' and '-' choices
⏱
Complexity
TimeO(2^n)
SpaceO(n) due to recursion stack

Each number doubles the number of expressions, leading to exponential growth.

💡 For n=20, this means over a million recursive calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature.

🧠
Top-Down DP with Memoization
💡 Memoization avoids recomputing the same states by caching results, drastically improving efficiency over brute force.

Intuition

Store results of recursive calls keyed by index and current sum to reuse when the same state is encountered again.

Algorithm

  1. Use a recursive function with parameters index and current sum.
  2. Check if the state (index, current sum) is in memo; if yes, return cached result.
  3. If index equals length of nums, return 1 if current sum equals target else 0.
  4. Recursively compute ways by adding and subtracting current number, store in memo, and return.
💡 Memoization prunes the recursion tree by avoiding repeated work, turning exponential time into polynomial.
Recurrence:f(i, sum) = f(i+1, sum + nums[i]) + f(i+1, sum - nums[i])
</>
Code
def findTargetSumWays(nums, target):
    memo = {}
    def backtrack(i, current_sum):
        if i == len(nums):
            return 1 if current_sum == target else 0
        if (i, current_sum) in memo:
            return memo[(i, current_sum)]
        memo[(i, current_sum)] = backtrack(i+1, current_sum + nums[i]) + backtrack(i+1, current_sum - nums[i])
        return memo[(i, current_sum)]

    return backtrack(0, 0)

# Example usage
if __name__ == '__main__':
    print(findTargetSumWays([1,1,1,1,1], 3))  # Output: 5
Line Notes
memo = {}Initialize cache to store computed states
if (i, current_sum) in memo:Check if result already computed to avoid recomputation
memo[(i, current_sum)] = ...Store computed result for current state
return memo[(i, current_sum)]Return cached or newly computed result
import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<String, Integer> memo = new HashMap<>();

    public int findTargetSumWays(int[] nums, int target) {
        return backtrack(nums, target, 0, 0);
    }

    private int backtrack(int[] nums, int target, int index, int currentSum) {
        if (index == nums.length) {
            return currentSum == target ? 1 : 0;
        }
        String key = index + "," + currentSum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int count = backtrack(nums, target, index + 1, currentSum + nums[index]) +
                    backtrack(nums, target, index + 1, currentSum - nums[index]);
        memo.put(key, count);
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findTargetSumWays(new int[]{1,1,1,1,1}, 3)); // 5
    }
}
Line Notes
private Map<String, Integer> memo = new HashMap<>();Cache to store results keyed by index and sum
String key = index + "," + currentSum;Create unique key for memoization
if (memo.containsKey(key))Return cached result if available
memo.put(key, count);Store computed count for current state
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, int> memo;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return backtrack(nums, target, 0, 0);
    }

private:
    int backtrack(vector<int>& nums, int target, int index, int currentSum) {
        if (index == nums.size()) {
            return currentSum == target ? 1 : 0;
        }
        string key = to_string(index) + "," + to_string(currentSum);
        if (memo.count(key)) return memo[key];
        memo[key] = backtrack(nums, target, index + 1, currentSum + nums[index]) +
                    backtrack(nums, target, index + 1, currentSum - nums[index]);
        return memo[key];
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,1,1,1,1};
    cout << sol.findTargetSumWays(nums, 3) << endl; // 5
    return 0;
}
Line Notes
unordered_map<string, int> memo;Cache to store computed states
string key = to_string(index) + "," + to_string(currentSum);Unique key for memoization
if (memo.count(key)) return memo[key];Return cached result if present
memo[key] = ...Store computed count for current state
function findTargetSumWays(nums, target) {
    const memo = new Map();
    function backtrack(i, currentSum) {
        if (i === nums.length) {
            return currentSum === target ? 1 : 0;
        }
        const key = i + ',' + currentSum;
        if (memo.has(key)) return memo.get(key);
        const count = backtrack(i + 1, currentSum + nums[i]) + backtrack(i + 1, currentSum - nums[i]);
        memo.set(key, count);
        return count;
    }
    return backtrack(0, 0);
}

// Example usage
console.log(findTargetSumWays([1,1,1,1,1], 3)); // 5
Line Notes
const memo = new Map();Initialize cache for memoization
const key = i + ',' + currentSum;Create unique key for current state
if (memo.has(key)) return memo.get(key);Return cached result if available
memo.set(key, count);Store computed count for reuse
⏱
Complexity
TimeO(n * sum(nums))
SpaceO(n * sum(nums)) for memo

Memoization prunes recursion to unique (index, sum) states bounded by n and sum of nums.

💡 For n=20 and sum=1000, this reduces calls from millions to about 20,000 states.
Interview Verdict: Accepted

Memoization is efficient enough for given constraints and is a common interview solution.

🧠
Bottom-Up DP (Tabulation)
💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion with memo.

Intuition

Use a 2D dp table where dp[i][sum] counts ways to reach sum using first i numbers, filling row by row.

Algorithm

  1. Calculate total sum of nums to determine dp array size and offset for negative sums.
  2. Initialize dp array with dp[0][offset] = 1 (0 elements sum to 0 in 1 way).
  3. Iterate over nums, for each number update dp[i][sum] by adding counts from dp[i-1][sum - nums[i-1]] and dp[i-1][sum + nums[i-1]].
  4. Return dp[n][target + offset] as the final count.
💡 The offset shifts sums to non-negative indices, enabling array indexing for negative sums.
Recurrence:dp[i][sum] = dp[i-1][sum - nums[i-1]] + dp[i-1][sum + nums[i-1]]
</>
Code
def findTargetSumWays(nums, target):
    total = sum(nums)
    offset = total
    n = len(nums)
    dp = [[0] * (2 * total + 1) for _ in range(n + 1)]
    dp[0][offset] = 1

    for i in range(1, n + 1):
        for s in range(2 * total + 1):
            if dp[i-1][s] != 0:
                if s + nums[i-1] <= 2 * total:
                    dp[i][s + nums[i-1]] += dp[i-1][s]
                if s - nums[i-1] >= 0:
                    dp[i][s - nums[i-1]] += dp[i-1][s]

    return dp[n][target + offset] if -total <= target <= total else 0

# Example usage
if __name__ == '__main__':
    print(findTargetSumWays([1,1,1,1,1], 3))  # Output: 5
Line Notes
total = sum(nums)Calculate sum to determine dp range
dp = [[0] * (2 * total + 1) for _ in range(n + 1)]Initialize dp table with offset for negative sums
dp[0][offset] = 1Base case: zero elements sum to zero in one way
dp[i][s + nums[i-1]] += dp[i-1][s]Add ways by adding current number
dp[i][s - nums[i-1]] += dp[i-1][s]Add ways by subtracting current number
public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int num : nums) total += num;
        int offset = total;
        int n = nums.length;
        int[][] dp = new int[n + 1][2 * total + 1];
        dp[0][offset] = 1;

        for (int i = 1; i <= n; i++) {
            for (int s = 0; s <= 2 * total; s++) {
                if (dp[i - 1][s] != 0) {
                    if (s + nums[i - 1] <= 2 * total) {
                        dp[i][s + nums[i - 1]] += dp[i - 1][s];
                    }
                    if (s - nums[i - 1] >= 0) {
                        dp[i][s - nums[i - 1]] += dp[i - 1][s];
                    }
                }
            }
        }

        return (target > total || target < -total) ? 0 : dp[n][target + offset];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findTargetSumWays(new int[]{1,1,1,1,1}, 3)); // 5
    }
}
Line Notes
int total = 0; for (int num : nums) total += num;Calculate total sum for dp size
int[][] dp = new int[n + 1][2 * total + 1];Create dp table with offset for negative sums
dp[0][offset] = 1;Base case: zero elements sum to zero
dp[i][s + nums[i - 1]] += dp[i - 1][s];Add ways by adding current number
dp[i][s - nums[i - 1]] += dp[i - 1][s];Add ways by subtracting current number
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0;
        for (int num : nums) total += num;
        int offset = total;
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(2 * total + 1, 0));
        dp[0][offset] = 1;

        for (int i = 1; i <= n; i++) {
            for (int s = 0; s <= 2 * total; s++) {
                if (dp[i - 1][s] != 0) {
                    if (s + nums[i - 1] <= 2 * total) {
                        dp[i][s + nums[i - 1]] += dp[i - 1][s];
                    }
                    if (s - nums[i - 1] >= 0) {
                        dp[i][s - nums[i - 1]] += dp[i - 1][s];
                    }
                }
            }
        }

        if (target > total || target < -total) return 0;
        return dp[n][target + offset];
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,1,1,1,1};
    cout << sol.findTargetSumWays(nums, 3) << endl; // 5
    return 0;
}
Line Notes
int total = 0; for (int num : nums) total += num;Calculate total sum for dp range
vector<vector<int>> dp(n + 1, vector<int>(2 * total + 1, 0));Initialize dp table with offset
dp[0][offset] = 1;Base case: zero elements sum to zero
dp[i][s + nums[i - 1]] += dp[i - 1][s];Add ways by adding current number
dp[i][s - nums[i - 1]] += dp[i - 1][s];Add ways by subtracting current number
function findTargetSumWays(nums, target) {
    const total = nums.reduce((a, b) => a + b, 0);
    const offset = total;
    const n = nums.length;
    const dp = Array.from({ length: n + 1 }, () => Array(2 * total + 1).fill(0));
    dp[0][offset] = 1;

    for (let i = 1; i <= n; i++) {
        for (let s = 0; s <= 2 * total; s++) {
            if (dp[i - 1][s] !== 0) {
                if (s + nums[i - 1] <= 2 * total) {
                    dp[i][s + nums[i - 1]] += dp[i - 1][s];
                }
                if (s - nums[i - 1] >= 0) {
                    dp[i][s - nums[i - 1]] += dp[i - 1][s];
                }
            }
        }
    }

    return (target > total || target < -total) ? 0 : dp[n][target + offset];
}

// Example usage
console.log(findTargetSumWays([1,1,1,1,1], 3)); // 5
Line Notes
const total = nums.reduce((a, b) => a + b, 0);Calculate total sum for dp size
const dp = Array.from({ length: n + 1 }, () => Array(2 * total + 1).fill(0));Initialize dp table with offset
dp[0][offset] = 1;Base case: zero elements sum to zero
dp[i][s + nums[i - 1]] += dp[i - 1][s];Add ways by adding current number
dp[i][s - nums[i - 1]] += dp[i - 1][s];Add ways by subtracting current number
⏱
Complexity
TimeO(n * sum(nums))
SpaceO(n * sum(nums))

We fill a dp table of size n by 2*total_sum, iterating over all states.

💡 For n=20 and sum=1000, this is about 40,000 operations, efficient for interviews.
Interview Verdict: Accepted

Tabulation is a robust and clear approach often preferred in interviews.

🧠
Space Optimized Bottom-Up DP (1D Array)
💡 We can reduce space by using a 1D dp array and iterating backwards to avoid overwriting needed states.

Intuition

Since dp[i] depends only on dp[i-1], we can use a single array and update it in reverse order to preserve previous iteration's data.

Algorithm

  1. Calculate total sum and offset for indexing.
  2. Initialize 1D dp array with dp[offset] = 1.
  3. For each number, iterate sums backwards from high to low to update dp for adding and subtracting current number.
  4. Return dp[target + offset] if valid, else 0.
💡 Backward iteration ensures we use previous iteration's dp values, preventing premature updates.
Recurrence:dp[sum] = dp[sum - nums[i]] + dp[sum + nums[i]] (using previous iteration values)
</>
Code
def findTargetSumWays(nums, target):
    total = sum(nums)
    offset = total
    dp = [0] * (2 * total + 1)
    dp[offset] = 1

    for num in nums:
        next_dp = [0] * (2 * total + 1)
        for s in range(2 * total + 1):
            if dp[s] != 0:
                if s + num <= 2 * total:
                    next_dp[s + num] += dp[s]
                if s - num >= 0:
                    next_dp[s - num] += dp[s]
        dp = next_dp

    return dp[target + offset] if -total <= target <= total else 0

# Example usage
if __name__ == '__main__':
    print(findTargetSumWays([1,1,1,1,1], 3))  # Output: 5
Line Notes
dp = [0] * (2 * total + 1)Initialize 1D dp array with offset for sums
dp[offset] = 1Base case: zero elements sum to zero
for s in range(2 * total + 1):Iterate over all possible sums
next_dp[s + num] += dp[s]Add ways by adding current number
next_dp[s - num] += dp[s]Add ways by subtracting current number
dp = next_dpUpdate dp to next iteration
public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int num : nums) total += num;
        int offset = total;
        int[] dp = new int[2 * total + 1];
        dp[offset] = 1;

        for (int num : nums) {
            int[] nextDp = new int[2 * total + 1];
            for (int s = 0; s <= 2 * total; s++) {
                if (dp[s] != 0) {
                    if (s + num <= 2 * total) nextDp[s + num] += dp[s];
                    if (s - num >= 0) nextDp[s - num] += dp[s];
                }
            }
            dp = nextDp;
        }

        return (target > total || target < -total) ? 0 : dp[target + offset];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findTargetSumWays(new int[]{1,1,1,1,1}, 3)); // 5
    }
}
Line Notes
int[] dp = new int[2 * total + 1];Initialize 1D dp array with offset
dp[offset] = 1;Base case: zero elements sum to zero
for (int s = 0; s <= 2 * total; s++)Iterate over all sums
nextDp[s + num] += dp[s];Add ways by adding current number
nextDp[s - num] += dp[s];Add ways by subtracting current number
dp = nextDp;Update dp for next iteration
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0;
        for (int num : nums) total += num;
        int offset = total;
        vector<int> dp(2 * total + 1, 0);
        dp[offset] = 1;

        for (int num : nums) {
            vector<int> nextDp(2 * total + 1, 0);
            for (int s = 0; s <= 2 * total; s++) {
                if (dp[s] != 0) {
                    if (s + num <= 2 * total) nextDp[s + num] += dp[s];
                    if (s - num >= 0) nextDp[s - num] += dp[s];
                }
            }
            dp = nextDp;
        }

        if (target > total || target < -total) return 0;
        return dp[target + offset];
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,1,1,1,1};
    cout << sol.findTargetSumWays(nums, 3) << endl; // 5
    return 0;
}
Line Notes
vector<int> dp(2 * total + 1, 0);Initialize 1D dp array with offset
dp[offset] = 1;Base case: zero elements sum to zero
for (int s = 0; s <= 2 * total; s++)Iterate over all sums
nextDp[s + num] += dp[s];Add ways by adding current number
nextDp[s - num] += dp[s];Add ways by subtracting current number
dp = nextDp;Update dp for next iteration
function findTargetSumWays(nums, target) {
    const total = nums.reduce((a, b) => a + b, 0);
    const offset = total;
    let dp = new Array(2 * total + 1).fill(0);
    dp[offset] = 1;

    for (const num of nums) {
        const nextDp = new Array(2 * total + 1).fill(0);
        for (let s = 0; s <= 2 * total; s++) {
            if (dp[s] !== 0) {
                if (s + num <= 2 * total) nextDp[s + num] += dp[s];
                if (s - num >= 0) nextDp[s - num] += dp[s];
            }
        }
        dp = nextDp;
    }

    return (target > total || target < -total) ? 0 : dp[target + offset];
}

// Example usage
console.log(findTargetSumWays([1,1,1,1,1], 3)); // 5
Line Notes
let dp = new Array(2 * total + 1).fill(0);Initialize 1D dp array with offset
dp[offset] = 1;Base case: zero elements sum to zero
for (let s = 0; s <= 2 * total; s++)Iterate over all sums
nextDp[s + num] += dp[s];Add ways by adding current number
nextDp[s - num] += dp[s];Add ways by subtracting current number
dp = nextDp;Update dp for next iteration
⏱
Complexity
TimeO(n * sum(nums))
SpaceO(sum(nums))

Space reduced from 2D to 1D array, iterating over sums for each number.

💡 For n=20 and sum=1000, space reduces from ~40,000 to ~2,000, improving memory efficiency.
Interview Verdict: Accepted

Space optimization is a valuable skill to demonstrate in interviews for DP problems.

📊
All Approaches - One-Glance Tradeoffs
💡 Memoization or bottom-up tabulation are best for interviews; brute force is for understanding; space optimization is a bonus.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Top-Down DP with MemoizationO(n * sum(nums))O(n * sum(nums)) memo + recursion stackNo (pruned recursion)YesCode if comfortable with recursion and memo
3. Bottom-Up DP (Tabulation)O(n * sum(nums))O(n * sum(nums))NoYesPreferred approach for clarity and iterative style
4. Space Optimized Bottom-Up DPO(n * sum(nums))O(sum(nums))NoHarderMention as optimization if time permits
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative clarity.Mention space optimization if time permits.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer checks problem understanding, ability to optimize naive solutions, and knowledge of DP patterns and space optimization.

Common Follow-ups

  • What if nums contain zeros? → zeros double the count of ways for sums they appear in.
  • Can we handle negative numbers in nums? → This approach assumes non-negative nums; negative nums complicate indexing.
  • How to reconstruct one valid expression? → Track choices during DP or memoization.
  • What if target is out of possible sum range? → Return 0 immediately.
💡 These follow-ups test deeper understanding of edge cases, input variations, and solution extensions.
🔍
Pattern Recognition

When to Use

1) Problem asks for ways to assign '+'/'-' signs or subsets to reach target sum; 2) Input size suggests exponential brute force; 3) Overlapping subproblems exist; 4) Problem can be reframed as subset sum or knapsack.

Signature Phrases

number of ways to assign '+' or '-'expressions that evaluate to target

NOT This Pattern When

Problems asking only for existence of subset sum or maximum/minimum sums without counting ways.

Similar Problems

Partition Equal Subset Sum - similar subset sum counting problemCoin Change 2 - counting ways to reach a target sumOnes and Zeroes - knapsack with multiple constraints

Practice

(1/5)
1. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array iterating coins first, then amounts
C. Backtracking exploring all permutations of coins to sum to the amount
D. Sorting coins and using two pointers to find pairs that sum to the amount

Solution

  1. Step 1: Understand problem constraints

    The problem requires counting unique combinations, not permutations, of coins to reach the target amount.
  2. Step 2: Identify algorithm that counts combinations without duplicates

    Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP with coin-first iteration counts combinations correctly [OK]
Hint: Coin-first DP avoids permutation overcounting [OK]
Common Mistakes:
  • Using greedy misses some combinations
  • Counting permutations instead of combinations
  • Using two pointers only works for pair sums
2. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.
B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.
C. A depth-first search that tries all subsets without memoization.
D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

  1. Step 1: Understand problem constraints

    The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.
  2. Step 2: Identify algorithm that guarantees correctness

    Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP tracks all sums up to target -> correct [OK]
Hint: Subset sum requires DP to track achievable sums [OK]
Common Mistakes:
  • Thinking greedy or sorting solves subset sum optimally
3. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?
medium
A. O(amount^2)
B. O(n + amount)
C. O(2^amount)
D. O(n * amount)

Solution

  1. Step 1: Identify loops in code

    Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.
  2. Step 2: Calculate complexity

    Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Nested loops over coins and amounts confirm O(n * amount) [OK]
Hint: Count nested loops and their ranges [OK]
Common Mistakes:
  • Confusing amount with n
  • Forgetting recursion stack space
  • Assuming quadratic in amount
4. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?
medium
A. O(n + sum)
B. O(n^2)
C. O(n * sum * log n)
D. O(n * sum)

Solution

  1. Step 1: Identify loops in the code

    Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).
  2. Step 2: Calculate total operations

    Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    DP complexity depends on n and sum, not n squared or log factors [OK]
Hint: DP loops over stones and sums -> O(n * sum) [OK]
Common Mistakes:
  • Confusing n with sum leading to O(n^2)
  • Assuming logarithmic factor due to sorting
  • Ignoring that dp array size depends on sum
5. Suppose the problem is modified so that jobs can be scheduled multiple times (i.e., unlimited reuse of the same job), still without overlapping. Which modification to the optimal DP approach is correct?
hard
A. Replace binary search with linear search to find compatible jobs and keep DP unchanged
B. Use a 1D DP array indexed by time and for each time, consider all jobs that can start then, allowing reuse
C. Keep the same DP with binary search but remove the skip option to always take the current job
D. Sort jobs by start time and use memoized recursion without binary search

Solution

  1. Step 1: Understand unlimited reuse impact

    Allowing multiple uses of the same job means the problem resembles unbounded interval scheduling with no overlaps.
  2. Step 2: Modify DP approach

    Use a 1D DP array indexed by time (e.g., dp[t] = max profit up to time t). For each time, consider all jobs starting at or after t, allowing reuse by updating dp[end_i] = max(dp[end_i], dp[start_i] + profit_i).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search and skip logic do not handle reuse; time-indexed DP handles multiple scheduling [OK]
Hint: Use time-indexed DP for unlimited job reuse [OK]
Common Mistakes:
  • Trying to reuse binary search DP without changes
  • Removing skip option breaks correctness
  • Sorting by start time only
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard