Subset Sum Problem: Complete Solution Guide

1. Introduction and Core Concepts

The subset sum problem is one of the most fundamental problems in computer science and dynamic programming. Given a set of non-negative integers and a target sum, the problem asks whether there exists a subset of the given set whose sum equals the target. Despite its simple statement, the subset sum problem encapsulates the core challenges of combinatorial optimization and serves as a gateway to understanding NP-complete problems.

Formally, given a set S = {a1, a2, ..., an} and an integer T, determine if there exists a subset S' ⊆ S such that the sum of elements in S' equals T. For example, with S = {3, 34, 4, 12, 5, 2} and T = 9, the answer is true because the subset {4, 5} sums to 9. For T = 30, no such subset exists. The empty subset is considered valid for T = 0, which forms an important base case for dynamic programming solutions.

Why does the subset sum problem matter? First, it is a special case of the 0/1 Knapsack problem where the value of each item equals its weight, and the knapsack capacity is the target sum. Second, it is NP-complete, meaning no known polynomial-time algorithm exists for all cases, yet it admits a pseudo-polynomial time dynamic programming solution that is highly efficient when the target sum is not excessively large. This makes it a perfect case study for understanding the trade-offs between brute force, memoization, and tabulation. Mastering this problem builds intuition for solving partition problems, coin change, and other subset-based optimization challenges that appear frequently in technical interviews and real-world systems.

Key Terminology and Problem Variants

Before diving into solutions, it is important to distinguish between the decision, search, and counting variants of the subset sum problem. The decision variant simply returns true or false — does a subset exist? The search variant requires reconstructing the actual subset if it exists. The counting variant asks how many distinct subsets sum to the target, while the optimization variant seeks the subset with sum closest to but not exceeding the target.

Another critical distinction is whether elements can be reused. In the classic subset sum problem, each element can be used at most once (0/1 property). If reuse is allowed, the problem becomes the unbounded subset sum or coin change problem, which has a different recurrence. Most interview questions focus on the 0/1 version without repetition, but you should always clarify this constraint with the interviewer.

The subset sum problem also assumes non-negative integers in its classic DP formulation. When negative numbers are allowed, the DP table must be shifted or alternative techniques like meet-in-the-middle are required, as the target range is no longer bounded between 0 and T. Understanding these assumptions is essential for choosing the correct algorithmic approach and avoiding subtle bugs.

2. How It Works

At its core, the subset sum problem exhibits two key properties that make it ideal for dynamic programming: optimal substructure and overlapping subproblems. Optimal substructure means that the solution to the larger problem can be constructed from solutions to smaller subproblems. Overlapping subproblems means the same subproblems are solved repeatedly in a naive recursive approach, creating an opportunity for memoization.

Consider the recursive decision: for the last element arr[n-1] and target T, we have two choices. If arr[n-1] > T, we must exclude it, and the problem reduces to subsetSum(n-1, T). Otherwise, we can either include it — reducing the problem to subsetSum(n-1, T - arr[n-1]) — or exclude it — subsetSum(n-1, T). The answer is true if either inclusion or exclusion leads to a solution. This binary choice creates a recursion tree of size O(2^n), which is exponential and impractical for n > 30.

Dynamic programming optimizes this by storing results of subproblems in a table. We define dp[i][j] as true if a subset of the first i elements can sum to j. The base cases are dp[i][0] = true for all i (empty subset sums to 0) and dp[0][j] = false for j > 0 (no elements cannot form a positive sum). The recurrence is: dp[i][j] = dp[i-1][j] OR dp[i-1][j - arr[i-1]] if arr[i-1] <= j, otherwise dp[i][j] = dp[i-1][j]. By filling this table bottom-up, we solve each subproblem once.

The DP State Transition in Depth

The power of the DP formulation lies in its systematic table filling. Imagine a 2D grid where rows represent elements considered and columns represent achievable sums from 0 to T. Each cell depends only on the cell directly above it (exclude case) and the cell diagonally up-left (include case). This dependency structure allows for both row-by-row iteration and space optimization.

A crucial insight is that the order of iteration matters for space optimization. When compressing the 2D table to a 1D array dp[j], we must iterate j backwards from T down to arr[i-1]. Forward iteration would incorrectly allow reuse of the same element multiple times, converting the 0/1 problem into an unbounded one. This subtle detail is a common source of bugs and interview follow-up questions.

The pseudo-polynomial nature of the algorithm deserves emphasis. The time complexity O(n*T) is polynomial in the numeric value of T, but exponential in the number of bits needed to represent T (log T). If T is very large (e.g., 10^9), the DP table becomes infeasible despite small n. In such cases, alternative algorithms like meet-in-the-middle with O(2^(n/2)) or branch-and-bound may be more appropriate. Recognizing when pseudo-polynomial is not truly polynomial is a mark of advanced understanding.

3. Implementation

Implementing the subset sum problem in Python offers an opportunity to demonstrate progression from exponential brute force to optimized dynamic programming. Below are four distinct implementations, each with detailed comments, illustrating different trade-offs in clarity, performance, and memory usage. All code escapes comparison operators for HTML safety while remaining executable when unescaped.

Approach 1: Brute Force Recursion (Exponential)

This baseline implementation directly translates the recursive definition. While simple, it recalculates the same subproblems many times and should only be used for understanding the recurrence or for very small inputs.

def is_subset_sum_recursive(arr, n, target):
    """
    Brute force recursive solution for subset sum.
    Args:
        arr: list of integers
        n: number of elements to consider (first n elements)
        target: desired sum
    Returns:
        True if subset exists, False otherwise
    """
    # Base case: target 0 means empty subset found
    if target == 0:
        return True
    # Base case: no elements left but target > 0
    if n == 0:
        return False
    
    # If last element is greater than target, skip it
    if arr[n-1] > target:
        return is_subset_sum_recursive(arr, n-1, target)
    
    # Try both choices: include or exclude last element
    include = is_subset_sum_recursive(arr, n-1, target - arr[n-1])
    exclude = is_subset_sum_recursive(arr, n-1, target)
    return include or exclude

# Example usage
arr = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_recursive(arr, len(arr), 9))   # True
print(is_subset_sum_recursive(arr, len(arr), 30))  # False

Approach 2: Top-Down Memoization

Memoization retains the recursive structure but caches results to avoid redundant computation. This is often the most intuitive DP conversion for interview settings because it requires minimal changes to the recursive code.

def is_subset_sum_memo(arr, target):
    """
    Top-down DP with memoization.
    Time: O(n * target), Space: O(n * target) for memo + recursion stack
    """
    n = len(arr)
    memo = {}  # key: (i, t) -> bool
    
    def dp(i, t):
        # i = number of elements considered, t = remaining target
        if t == 0:
            return True
        if i == 0:
            return False
        if (i, t) in memo:
            return memo[(i, t)]
        
        # Decision: skip if element too large
        if arr[i-1] > t:
            result = dp(i-1, t)
        else:
            # Include or exclude
            result = dp(i-1, t) or dp(i-1, t - arr[i-1])
        
        memo[(i, t)] = result
        return result
    
    return dp(n, target)

# Example: handles larger inputs efficiently
arr = [3, 34, 4, 12, 5, 2]
print(is_subset_sum_memo(arr, 9))  # True
print(is_subset_sum_memo(arr, 13)) # True (4+5+4? No, 3+5+2+? Actually 3+4+5+? Let's test 12+? )

Approach 3: Bottom-Up Tabulation (2D DP)

Tabulation is the most common interview-expected solution. It iteratively builds a table without recursion, avoiding stack overflow and making the data flow explicit. This version also makes subset reconstruction straightforward.

def is_subset_sum_dp(arr, target):
    """
    Bottom-up DP with 2D table.
    dp[i][j] = True if subset of first i elements sums to j
    Time: O(n * target), Space: O(n * target)
    """
    n = len(arr)
    # Initialize DP table (n+1) x (target+1)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # Base case: target 0 is always achievable
    for i in range(n + 1):
        dp[i][0] = True
    
    # Fill table row by row
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if arr[i-1] > j:
                # Cannot include current element
                dp[i][j] = dp[i-1][j]
            else:
                # Include or exclude
                dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]
    
    return dp[n][target]

# Test with edge cases
print(is_subset_sum_dp([1, 2, 3], 5))  # True (2+3)
print(is_subset_sum_dp([1, 2, 3], 7))  # False
print(is_subset_sum_dp([], 0))         # True

Approach 4: Space-Optimized DP with Reconstruction

The 2D table can be compressed to 1D since each row only depends on the previous row. This reduces space from O(n*T) to O(T). The reconstruction logic requires careful handling and is often asked as a follow-up.

def subset_sum_optimized(arr, target):
    """
    Space-optimized DP + subset reconstruction.
    Time: O(n * target), Space: O(target) for decision, O(n*target) for reconstruction
    """
    n = len(arr)
    # 1D DP for decision
    dp = [False] * (target + 1)
    dp[0] = True
    
    # Fill 1D DP (backwards to avoid reuse)
    for num in arr:
        # Iterate backwards to ensure 0/1 property
        for j in range(target, num - 1, -1):
            if dp[j - num]:
                dp[j] = True
    
    if not dp[target]:
        return False, []
    
    # For reconstruction, rebuild full table (or store parent pointers)
    # Rebuilding is clearer for interviews
    full = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        full[i][0] = True
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if arr[i-1] > j:
                full[i][j] = full[i-1][j]
            else:
                full[i][j] = full[i-1][j] or full[i-1][j - arr[i-1]]
    
    # Backtrack to find subset
    subset = []
    i, j = n, target
    while i > 0 and j > 0:
        # If full[i-1][j] is False, then arr[i-1] was included
        if not full[i-1][j]:
            subset.append(arr[i-1])
            j -= arr[i-1]
        i -= 1
    
    return True, subset[::-1]

# Example with reconstruction
found, subset = subset_sum_optimized([3, 34, 4, 12, 5, 2], 9)
print(found, subset)  # True, [4, 5] (or [3, 4, 2])

def count_subsets(arr, target):
    """Counting variant: number of subsets that sum to target"""
    dp = [0] * (target + 1)
    dp[0] = 1  # One way to make sum 0
    for num in arr:
        for j in range(target, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[target]

print(count_subsets([1, 1, 2, 3], 4))  # 3 ways: [1,1,2], [1,3] (x2 due to two 1s)

4. Step-by-Step Example

To solidify understanding, let us walk through a complete bottom-up DP execution for the classic example: arr = [3, 2, 5] and target = 7. We will build the DP table manually, showing how each cell is computed and how the final answer is derived.

We create a table with n+1 = 4 rows (including 0 elements) and target+1 = 8 columns (sums 0 to 7). Initialize all dp[i][0] = True because sum 0 is always possible with an empty subset. All dp[0][j] = False for j > 0. The table starts as:

Row 0 (no elements): [T, F, F, F, F, F, F, F]

Now we iterate. For i=1 (element 3): For j from 1 to 7, if 3 > j, copy from above. For j=3, dp[1][3] = dp[0][3] or dp[0][0] = F or T = T. Similarly j=5 stays F, but j=3 becomes T. Row 1 becomes [T, F, F, T, F, F, F, F]. This indicates with {3}, we can make sums 0 and 3.

For i=2 (element 2): For j=2, dp[2][2] = dp[1][2] or dp[1][0] = F or T = T. For j=5, dp[2][5] = dp[1][5] or dp[1][3] = F or T = T (3+2). For j=3, dp[2][3] = dp[1][3] or dp[1][1] = T or F = T (still achievable). Row 2 becomes [T, F, T, T, F, T, F, F], representing achievable sums {0,2,3,5} with {3,2}.

Completing the Table and Backtracking

For i=3 (element 5): Compute each j. j=5 is already T, stays T. j=7 is key: dp[3][7] = dp[2][7] or dp[2][2] = F or T = T because dp[2][2] is T (subset {2} sums to 2, plus 5 gives 7). j=8 would be out of range, but j=7 now true indicates success. Row 3 final: [T, F, T, T, F, T, F, T]. Since dp[3][7] = True, a subset exists.

To reconstruct the subset, we backtrack from dp[3][7]. Check if dp[2][7] is True? It is False, so element 5 must have been included. We add 5 to subset and move to dp[2][2] (7-5=2). At dp[2][2], check dp[1][2] which is False, so element 2 was included. Move to dp[1][0] which is base case. Subset is {5,2} which sums to 7. Alternative path could find {2,5} same set.

This walkthrough reveals why the table is filled row by row: each row represents the closure of achievable sums after considering one more element. The final column tells us feasibility, while the path through the table tells us construction. Visualizing this process is invaluable for debugging — if you print the DP table during development, patterns like monotonic propagation of True values become immediately apparent.

5. Complexity Analysis

Understanding the complexity of the subset sum problem requires distinguishing between input size measured in bits versus numeric value. The algorithm's performance depends on both n (number of elements) and T (target sum), leading to what is known as pseudo-polynomial complexity.

The brute force recursive solution explores a binary decision tree of depth n, resulting in O(2^n) time and O(n) recursion stack space. While its best case may early-exit if a solution is found quickly, its worst and average cases remain exponential. This approach is only viable for n < 25 in practice and serves primarily as a pedagogical baseline.

Dynamic programming solutions dramatically improve time at the cost of space. Both memoization and tabulation achieve O(n*T) time because they compute at most (n+1)*(T+1) distinct states, each in O(1). The difference lies in overhead: memoization has recursion overhead and may not visit all states if early pruning occurs, while tabulation always fills the entire table but has better constant factors and no recursion limits. Space-optimized DP reduces memory from O(n*T) to O(T) by reusing a single array, though reconstruction still requires O(n*T) if the subset itself is needed.

Pseudo-Polynomial vs Truly Polynomial

It is critical to understand why O(n*T) is not considered polynomial in the strict complexity-theoretic sense. The input size is measured in bits: representing T requires O(log T) bits, but the algorithm runs in time proportional to T itself, which is exponential in log T. For example, if T = 1,000,000, the table has one million columns even though T is represented with only 20 bits. When T is bounded by a polynomial in n (e.g., T ≤ n^2), the algorithm is effectively polynomial. When T can be arbitrarily large (e.g., up to 2^n), the DP becomes infeasible.

Meet-in-the-middle provides an alternative for large T but moderate n (n ≤ 40). It splits the set into two halves, enumerates all 2^(n/2) subset sums for each half, sorts one half, and then for each sum in the first half checks if T - sum exists in the second half via binary search. This achieves O(2^(n/2) * n) time and is independent of T, making it superior when T is huge. The choice between DP and meet-in-the-middle hinges on the relative magnitudes of n and T — a key design decision in system-level optimization.

For practical engineering, also consider cache performance. The 2D DP table accessed row-wise has excellent spatial locality, while the 1D optimized version iterating backwards may have slightly worse locality but far lower memory footprint. For T up to 10^5 and n up to 10^3, the 1D version is almost always preferred in production Python code due to memory constraints.

6. Variations and Optimizations

The classic subset sum problem has numerous variations that extend its utility and challenge its implementation. Understanding these variants not only prepares you for interview twists but also equips you to adapt the core DP pattern to real-world constraints.

The Partition Problem asks whether a set can be partitioned into two subsets with equal sum. This reduces to subset sum with target = sum(arr)/2, but only if the total sum is even. The Subset Sum with Given Difference asks for subsets where the difference between two partitions equals a target, which transforms to finding a subset with sum (total + diff)/2. The Count Subsets variant, shown in the code above, changes the boolean OR to integer addition, counting distinct subsets. The Minimum Subset Sum Difference seeks the partition minimizing the difference, solved by finding the largest j ≤ total/2 where dp[n][j] is true.

Handling negative numbers requires a shift in DP indexing. If the array contains negatives, the achievable sum range is no longer [0, T] but [min_sum, max_sum] where min_sum is the sum of all negative numbers. We offset the DP array by -min_sum so that index 0 corresponds to the most negative sum. This increases the table width to max_sum - min_sum + 1, which can be large, often making meet-in-the-middle or branch-and-bound more practical.

Another optimization is bitset optimization using Python integers as bitsets. Since dp[j] is boolean, we can represent the entire DP row as a bitset where bit j indicates achievability. The transition dp = dp | (dp << num) performs the include/exclude operation in parallel using bitwise shifts, which are implemented in C and extremely fast. For T up to 10^5, this can be 10-100x faster than nested loops, though it sacrifices reconstruction ability.

Advanced Techniques and Heuristics

For very large n and T, approximation algorithms become relevant. The Fully Polynomial Time Approximation Scheme (FPTAS) for subset sum can find a subset within (1 - ε) of the optimal in time polynomial in n and 1/ε by trimming the list of achievable sums to keep it polynomially bounded. This is useful in resource allocation where near-optimal is acceptable.

Early termination heuristics can also prune search dramatically. Sorting the array descending and using branch-and-bound with upper bounds (remaining sum) can cut the recursion tree significantly. If the sum of remaining elements plus current sum cannot reach T, prune that branch. Similarly, if current sum already exceeds T (for non-negative numbers), prune. These heuristics are essential for backtracking solutions in competitive programming when DP is memory-limited.

Finally, consider the unbounded variant where each element can be used infinitely many times. The recurrence changes to dp[i][j] = dp[i-1][j] or dp[i][j - arr[i-1]] — note the dp[i] not dp[i-1] in the second term, allowing reuse. The 1D implementation then iterates j forwards instead of backwards. Confusing these iteration directions is one of the most common implementation errors, so memorizing the pattern — backward for 0/1, forward for unbounded — is crucial.

7. Real-World Applications

While the subset sum problem appears abstract, its pattern underlies numerous practical systems in web infrastructure, finance, and operations. Recognizing when a real-world task maps to subset sum allows you to apply proven DP solutions rather than reinventing exponential search.

In web servers and load balancing, subset sum models task allocation. Suppose a server has a capacity T (CPU seconds or memory) and a queue of jobs with resource requirements arr[i]. Determining whether a subset of jobs can exactly fill the server without exceeding capacity is subset sum. Similarly, in container orchestration (Kubernetes), scheduling pods onto nodes with exact resource fitting uses subset sum logic to minimize fragmentation. The optimization variant — finding the subset closest to capacity — directly maximizes utilization.

In databases and storage systems, subset sum appears in backup and sharding. Selecting a subset of database partitions to replicate such that total size equals available backup storage, or choosing which indexes to keep in a memory budget, are subset sum decisions. Log-structured merge trees and compaction strategies also use subset sum to decide which SSTables to merge to achieve a target size tier.

In networks and cryptography, subset sum is famous for its role in the Merkle-Hellman knapsack cryptosystem, where the public key is a superincreasing sequence disguised via modular multiplication. Breaking the cryptosystem reduces to solving subset sum, which is hard for general instances but easy for superincreasing ones. In network packet scheduling, selecting packets to forward within a time window or MTU limit is another instance.

From Theory to Production

In production, the decision variant is rarely enough; you need the actual subset for action. For example, a budget allocation tool must not only tell a manager that a $50k budget can be met with available projects, but also which projects to fund. Hence, reconstruction logic is not optional in real systems, even though many tutorials omit it. Always implement parent pointers or backtracking tables if the solution will be acted upon.

Another production consideration is handling duplicates and large inputs. Real datasets often contain duplicate values (e.g., many 4GB VMs), which the counting variant must handle correctly without double-counting identical subsets that differ only by permutation. Using DP that iterates over elements rather than values naturally handles duplicates as distinct items, which is usually the desired semantics for resource allocation.

Finally, subset sum solutions are often composed into larger pipelines. For instance, a cloud scheduler might run subset sum repeatedly to pack multiple hosts (a bin packing heuristic), or a financial risk engine might run it for many target values to generate an efficient frontier. In these loops, the bitset optimization and caching of DP tables across runs become critical for latency. Understanding the core algorithm's performance characteristics enables you to predict and optimize system-level throughput.

8. Comparison with Alternatives

The subset sum problem does not exist in isolation; it is part of a family of knapsack and combinatorial problems that share DP structure but differ in objectives and constraints. Choosing the right model is essential for correct problem formulation and efficient solution.

The 0/1 Knapsack problem generalizes subset sum by adding values: each item has weight w[i] and value v[i], and we maximize total value without exceeding capacity W. Subset sum is the special case where v[i] = w[i] and we ask if value = W is achievable. Coin Change counts the number of ways to make amount T with unlimited coins, while Subset Sum limits each coin to one use. The Partition Problem is subset sum with T = sum/2. Understanding these reductions allows you to reuse code and reasoning across problems.

Alternative algorithmic paradigms also compete with DP. Greedy algorithms (sort descending and pick if fits) are fast O(n log n) but fail for subset sum — e.g., arr=[3,4,5], T=7, greedy picks 5 then cannot pick 3 or 4, but optimal is 3+4. Backtracking with pruning can be faster than DP when T is huge but n is small, as it explores only promising branches. Meet-in-the-middle excels when n ≤ 34 and T is large, while DP excels when T is moderate (≤ 10^5) regardless of n.

When to Choose Which Approach

If your problem asks “can we achieve exactly T?” with each element used once, use subset sum. If it asks “what is the maximum value we can achieve without exceeding W?” use knapsack. If it asks “how many ways can we make T with unlimited coins?” use coin change. Misclassifying the problem leads to incorrect DP dimensions and iteration orders, which are the most common sources of wrong answers in interviews.

For implementation, prefer bottom-up DP when you need to reconstruct the solution or when recursion depth may exceed Python's limit (n > 1000). Prefer memoization when the state space is sparse — e.g., when many j values are unreachable, memoization avoids computing them, while tabulation computes all. In practice, for subset sum with dense T, tabulation is usually faster in Python due to lower function call overhead.

Finally, consider language-specific optimizations. In Python, using a Python set to store achievable sums (reachable = {0}; for num in arr: reachable |= {x+num for x in reachable if x+num <= T}) can be surprisingly efficient for small n and large T because it only stores reachable sums, not all T possibilities. This set-based DP is O(n * number_of_reachable) and can beat array DP when T is huge but reachable sums are sparse. Knowing this trick demonstrates deep practical fluency beyond textbook DP.

9. Common Mistakes and Best Practices

Even experienced engineers stumble on subtle pitfalls when implementing subset sum. Awareness of these mistakes, coupled with disciplined best practices, separates a correct solution from one that passes only sample tests.

Mistake 1: Incorrect Base Cases. Forgetting that dp[i][0] = True for all i or that dp[0][0] = True leads to false negatives for target 0. Similarly, initializing the entire table to False and then not setting the first column breaks the recurrence. Always explicitly handle the empty subset case, and test with target=0 and arr=[].

Mistake 2: Forward Iteration in 1D DP. Iterating j from arr[i-1] to T in the 1D array reuses the same element multiple times, silently converting 0/1 to unbounded. The correct 0/1 iteration is backwards: for j in range(T, arr[i-1]-1, -1). This is the single most frequent bug in interviews. If you remember one rule, remember “0/1 goes backwards.”

Mistake 3: Off-by-One and Index Confusion. Mixing 0-based arr indexing with 1-based DP rows causes arr[i] vs arr[i-1] errors. Define clearly that dp[i][j] uses first i elements, so the i-th element is arr[i-1]. Write a comment stating this invariant at the top of your loop.

Mistake 4: Ignoring Integer Overflow and Large T. In languages like Java or C++, target up to 10^5 with n=100 creates a 10^7 cell table, which may exceed memory. In Python, a list of lists with 10^7 booleans is ~80MB and may cause MemoryError. Always check constraints and switch to 1D or bitset optimization when T > 10^5. Also, be aware that recursion depth > 1000 will hit Python's recursion limit for memoization.

Best Practices for Robust Code

• Validate Inputs Early: Check for negative target (return False unless handling negatives), empty array, and non-integer inputs. Raise ValueError for invalid types to fail fast.
• Use Descriptive Variable Names: Prefer dp, num_elements, target_sum over a, b, c. Clear names make the recurrence self-documenting.
• Modularize Decision vs Reconstruction: Write one function that returns boolean and another that returns the subset. This separation of concerns simplifies testing and reuse.
• Test Edge Cases Systematically: Include tests for target 0, target > sum(arr), single element equal to target, duplicates, and large random arrays with brute force verification for small n.
• Document Time-Space Trade-offs: Add a docstring stating complexity and when to use the function. This helps teammates choose the right variant without reading the implementation.
• Leverage Python Idioms: For quick prototyping, use any() with generator expressions or set-based DP for readability. For production, use array DP for predictability.

A final best practice is to always consider whether you need to handle the “closest sum ≤ T” variant. Many real problems do not require exact equality but want the best achievable sum under T. This is solved by scanning the last DP row for the largest j ≤ T where dp[n][j] is True, rather than just checking dp[n][T]. Implementing this scan adds one line but dramatically increases the utility of your function.

10. Interview Questions

Interviewers love the subset sum problem because it tests recursion, DP, optimization, and problem reduction in a single package. Below are five common questions, with hints on what interviewers look for and how to structure your answer.

Q1: Can you determine if an array can be partitioned into two subsets with equal sum?

This is the Partition Problem, a direct reduction to subset sum. First, compute total sum. If total is odd, return False. Otherwise, target = total // 2 and run subset sum DP. Interviewers check if you recognize the reduction and handle the odd case. Follow-up: reconstruct the partition — backtrack from dp[n][target] to find one subset, the other is the complement. Complexity is O(n*sum). Be ready to discuss why this is pseudo-polynomial and when it fails for large sums.

Q2: How would you count the number of subsets that sum to a target, handling duplicates?

Here the DP value becomes an integer count, not boolean. Initialize dp[0]=1, and for each num, iterate j backwards: dp[j] += dp[j-num]. The key nuance is that duplicates are considered distinct if they come from different indices — e.g., [1,1,2] with target 2 has two ways using each 1 separately plus one way using 2. If the question asks for distinct value combinations ignoring index, you need to deduplicate or sort and skip duplicates, which is more complex. Clarify the requirement before coding.

Q3: What if the array contains negative numbers? How does your DP change?

This tests understanding of DP bounds. With negatives, the sum range is [sum(negatives), sum(positives)]. You offset the DP array by -min_sum so index 0 represents the minimum achievable sum. The table size becomes (max_sum - min_sum + 1), which can be large. Alternative approaches: use memoization with a dictionary keyed by (i, sum) which only stores reachable sums, or use meet-in-the-middle. Strong candidates discuss both the offset technique and its memory implications, and propose the dictionary memo as a sparse alternative.

Q4: Optimize space to O(T). Can you still reconstruct the subset?

The 1D DP optimization is standard, but reconstruction is the twist. Pure 1D loses parent information. Solutions: (1) keep a separate parent table of size n*T storing decisions, still O(n*T) but only booleans; (2) rebuild the full table after decision (as shown in