Subset Sum Problem: Dynamic Programming, Code, and Complexity

The subset sum problem has one clear question: given an integer array, does any subset of its elements add up to a target value S?

It’s a placement-prep staple for a reason. The problem sits at the intersection of array manipulation and dynamic programming: two topics that appear in AMCAT, eLitmus, and every major IT services hiring test. Knowing both the 2-D table approach and the space-optimised 1-D version is the difference between a partial answer and a complete one when the interviewer asks “can you do better on memory?”

What Is the Subset Sum Problem?

Given a set of non-negative integers and a target sum S, determine whether a subset exists whose elements sum to exactly S.

A worked example:

• Array: [18, 23, 17, 29, 1, 6, 7, 30, 7, 6]
• Target S: 100
• Answer: Yes
• Subset: 18 + 23 + 17 + 29 + 6 + 7 = 100

Verify step by step:

• Step 1: 18 + 23 = 41
• Step 2: 41 + 17 = 58
• Step 3: 58 + 29 = 87
• Step 4: 87 + 6 = 93
• Step 5: 93 + 7 = 100

The subset {18, 23, 17, 29, 6, 7} works. Note that each element can be used at most once (this is the 0/1 variant, the most common interview form).

The brute-force approach checks all 2^n subsets. For 10 elements that’s 2^10 = 1024 checks, which is manageable. For 40 elements it’s over a trillion. Dynamic programming replaces that exponential search with a polynomial table-fill.

Dynamic Programming Approach

The key insight is optimal substructure: table[i][j] (does any subset of the first j elements sum to i?) can be computed from previously computed values.

The recurrence:

• Base case 1: table[0][j] = true for all j (empty subset sums to 0)
• Base case 2: table[i][0] = false for all i > 0 (no elements, non-zero target)
• If arr[j-1] > i: table[i][j] = table[i][j-1] (element too large, must exclude)
• Otherwise: table[i][j] = table[i][j-1] OR table[i - arr[j-1]][j-1]

The last case is the core: either exclude the current element (use the answer for the previous j-1 elements) or include it (look up whether the remaining sum i - arr[j-1] was achievable without this element).

The Introduction to Algorithms (CLRS), 4th ed. treats this as the canonical example of a pseudo-polynomial DP.

Step-by-Step Walkthrough

Small example: array [3, 4, 5], target S = 7.

Build a table with rows 0 to 7 (sums) and columns 0 to 3 (element count):

        0    1(3)  2(4)  3(5)
Sum=0   T    T     T     T
Sum=1   F    F     F     F
Sum=2   F    F     F     F
Sum=3   F    T     T     T
Sum=4   F    F     T     T
Sum=5   F    F     F     T
Sum=6   F    F     F     F
Sum=7   F    F     T     T

Reading off table[7][3] gives True (subset {3, 4} sums to 7).

Trace for table[7][2] (can we reach 7 using elements {3, 4}?):

• Step 1: Element 4 (arr[1] = 4) is ≤ 7, so check table[7][1] (exclude 4) OR table[3][1] (include 4).
• Step 2: table[7][1] = False, table[3][1] = True, so result is True.

This is the tabulation (bottom-up) method. FACE Prep’s space complexity guide explains why bottom-up is preferred over memoisation for bounded-integer DP problems.

Code Implementation

Python (2-D table)

def subset_sum(arr, target):
    n = len(arr)
    # table[i][j] = True if subset of arr[0..j-1] sums to i
    table = [[False] * (n + 1) for _ in range(target + 1)]

    # Sum 0 is always achievable (empty subset)
    for j in range(n + 1):
        table[0][j] = True

    for i in range(1, target + 1):
        for j in range(1, n + 1):
            # Exclude current element
            table[i][j] = table[i][j - 1]
            # Include current element if it fits
            if arr[j - 1] <= i:
                table[i][j] = table[i][j] or table[i - arr[j - 1]][j - 1]

    return table[target][n]


# Example from the FACE Prep walkthrough
arr = [18, 23, 17, 29, 1, 6, 7, 30, 7, 6]
print(subset_sum(arr, 100))  # True

Java (2-D table)

public class SubsetSum {
    public static boolean subsetSum(int[] arr, int target) {
        int n = arr.length;
        boolean[][] table = new boolean[target + 1][n + 1];

        // Sum 0 is achievable with any prefix (empty subset)
        for (int j = 0; j <= n; j++) table[0][j] = true;

        for (int i = 1; i <= target; i++) {
            for (int j = 1; j <= n; j++) {
                table[i][j] = table[i][j - 1];
                if (arr[j - 1] <= i) {
                    table[i][j] = table[i][j] || table[i - arr[j - 1]][j - 1];
                }
            }
        }
        return table[target][n];
    }

    public static void main(String[] args) {
        int[] arr = {18, 23, 17, 29, 1, 6, 7, 30, 7, 6};
        System.out.println(subsetSum(arr, 100));  // true
    }
}

Space-Optimised Python (1-D array)

def subset_sum_optimised(arr, target):
    dp = [False] * (target + 1)
    dp[0] = True  # empty subset

    for num in arr:
        # Iterate right-to-left to prevent reusing the same element
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

The right-to-left traversal is the key detail. Left-to-right would let a single element contribute more than once, turning the 0/1 variant into an unbounded knapsack. Interviewers specifically ask why the order matters.

Time and Space Complexity

Version	Time	Space
2-D DP table	O(n x S)	O(n x S)
1-D optimised	O(n x S)	O(S)
Brute force (all subsets)	O(2^n)	O(n) recursion stack

For AMCAT or campus placement tests, a typical problem has n at most 100 and S at most 10000, which makes the 2-D table perfectly acceptable. If the interviewer constrains memory, the 1-D version is the expected answer.

Understanding this trade-off connects directly to array algorithms like equilibrium index, where O(n) space reduction tricks follow the same right-to-left scanning pattern.

For a broader view of how space complexity is classified and compared across algorithms, see FACE Prep’s space complexity guide.

The problem is NP-complete in the general (unbounded S) sense, as detailed in GeeksforGeeks’ canonical writeup on Subset Sum (DP-25). For placement purposes, the bounded-S DP solution is what matters.

Common Interview Variants

These four variants appear regularly at Tier-2 campus drives:

• Partition Equal Subset Sum — can the array be split into two subsets with equal sums? Reduce to: is there a subset summing to total/2?
• Count of Subsets — instead of True/False, count how many subsets sum to S. Change the DP value type from bool to int; the recurrence becomes addition.
• Minimum Subset Sum Difference — partition the array to minimise the absolute difference between two subset sums. Solve subset sum for all targets 0 to total/2, then find the maximum achievable sum that does not exceed total/2.
• Target Sum (assign +/- signs) — equivalent to count of subsets summing to (total + target) / 2.

The symmetric pairs in array problem is a different array technique (hashing vs. DP), but both follow the same pattern of reducing a subset question to a lookup structure; worth knowing the contrast going into a placement round.

The Space Optimisation Argument at Interviews

Interviewers at product and AI-adjacent companies often stop at the O(S) version and ask: what happens if S is very large? That’s the NP-completeness boundary. The DP solution is polynomial in both n and S, but if S grows exponentially with n, the table itself becomes exponentially large.

In practice, placement tests cap S at values where the DP table fits in memory. Knowing the boundary is the signal that separates a student who has thought about the problem from one who has only memorised the code.

The subset sum pattern (tracking reachable states in a 1-D boolean array) directly shows up in LLM inference batching logic, where a scheduler tracks which batch-size configurations fit within a memory budget. If you’ve internalised the right-to-left update rule, that transition to systems-level thinking is shorter than it looks. TinkerLLM lets you experiment with that connection at ₹299; start with the DP-to-systems module and run your first batch-scheduling notebook in one session.