Target Sum

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n * sum(nums))	O(n * sum(nums)) memo + recursion stack	No (pruned recursion)	Yes	Code if comfortable with recursion and memo
3. Bottom-Up DP (Tabulation)	O(n * sum(nums))	O(n * sum(nums))	No	Yes	Preferred approach for clarity and iterative style
4. Space Optimized Bottom-Up DP	O(n * sum(nums))	O(sum(nums))	No	Harder	Mention 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. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?

easy

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0] since dp[0]=1.

2. Step 2: Update dp for each coin

   For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   dp[5] = 4 matches known output [OK]

Hint: Trace dp updates coin by coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Confusing permutations with combinations

2. You need to find the minimum number of coins required to make up a given amount from an unlimited supply of given coin denominations. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that picks the largest coin first until the amount is reached

B. Dynamic programming using a 1D array to store minimum coins needed for all amounts up to the target

C. Pure brute force recursion trying all combinations without memoization

D. Sorting coins and using binary search to find the best coin for each sub-amount

Solution

1. Step 1: Understand problem constraints

   The problem requires minimum coins for any amount with unlimited coin usage, which fits unbounded knapsack pattern.

2. Step 2: Identify algorithm that guarantees optimality

   Greedy fails for some coin sets; brute force is correct but inefficient; DP with 1D array efficiently computes minimum coins for all sub-amounts ensuring optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP solves overlapping subproblems optimally [OK]

Hint: Unbounded knapsack DP ensures optimal minimum coins [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring memoization for efficiency

3. 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

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the minimum subset sum difference problem, given an input array of size n and total sum S?

medium

A. O(S^2)

B. O(n^2)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each element), inner loop runs up to total_sum S times.

2. Step 2: Calculate total complexity

   Time complexity is O(n * S) because each element updates dp array of size S.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP iterates over n elements and sums up to S [OK]

Hint: Time depends on n and total sum, not n squared [OK]

Common Mistakes:

• Confusing n with S or assuming quadratic n^2
• Ignoring dp array size impact

5. The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

medium

A. Line: dp = [-1] * (1 << n)

B. Line: if dp[next_mask] == -1: (missing in this code)

C. Line: nums.sort()

D. Line: dp[next_mask] = (dp[mask] + nums[i]) % target

Solution

1. Step 1: Identify missing condition

   The code lacks a check if dp[next_mask] is already set, so it overwrites states, causing incorrect results.

2. Step 2: Pinpoint the buggy line

   The line assigning dp[next_mask] unconditionally overwrites previous valid states, breaking memoization.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding "if dp[next_mask] == -1:" before assignment fixes bug [OK]

Hint: Always check if dp state is unset before assignment [OK]

Common Mistakes:

• Overwriting dp states without checking leads to incorrect answers
• Not pruning symmetric states increases runtime