How to solve the subset sum problem with dynamic programming

The subset sum problem asks whether a collection of numbers contains a subset whose values add up to a specified target. Each item can usually be selected once or left out, so the challenge is to explore many possible combinations without repeatedly solving the same smaller problems.

Dynamic programming turns this exponential search into a manageable table-based algorithm for many practical inputs. The method is useful in programming interviews, LeetCode-style exercises, budgeting tools, resource allocation, and introductory algorithm courses. It also provides a clear example of how a carefully chosen state can remove duplicate work.

Understanding the subset sum problem

Given an array of non-negative integers and a target sum, the decision version of the problem returns True if some subset totals the target and False otherwise. For example, with values [3, 5, 7, 10] and target 15, the answer is True because 5 + 10 = 15.

A subset does not need to contain adjacent elements, and the original order does not matter. Each value is generally available once. This differs from the coin change problem, where a denomination may often be reused repeatedly. Clarifying that distinction prevents an incorrect recurrence or implementation.

Imagine checking whether selected prices from a small grocery basket in Sydney can total exactly A$20. The same reasoning applies to cents, weights, time slots, or file sizes, provided the values can be represented as suitable integers. For broader algorithm context, the data structures guide provides useful background on arrays, indexing, and memory-oriented representations.

Finding the right dynamic programming state

Define dp[s] as a Boolean value indicating whether it is possible to form sum s using the values processed so far. Initially, sum zero is always achievable by choosing the empty subset, so dp[0] = True. Every other entry starts as False.

When processing a number x, a previously achievable sum s can produce a new sum s + x. The target only requires sums from zero through target, so the table needs target + 1 entries. This is the key compression: instead of recording every subset, the algorithm records only which totals are reachable.

The state has a useful invariant: after processing the first i values, dp[s] is true precisely when some subset of those i values has sum s. Maintaining this invariant makes the recurrence easier to derive and gives a reliable way to test the code.

Deriving the recurrence

For each number x, every existing subset has two choices: exclude x or include it. Excluding it leaves all previous states unchanged. Including it changes a reachable sum s into s + x. In two-dimensional notation, the recurrence can be written as:

dp[i][s] = dp[i - 1][s] OR dp[i - 1][s - values[i]]

The first term represents leaving the current value out. The second represents selecting it, assuming s - values[i] was reachable before the value was considered. A two-dimensional table makes this relationship explicit but uses O(n × target) memory.

A one-dimensional table is enough because each row depends only on the previous row. However, the update must scan sums downwards, from target to x. If it scanned upwards, a value could be used to create a sum and then immediately reused during the same iteration, accidentally turning the problem into an unlimited-use variant.

For example, if x = 4, update dp[12] from dp[8], then dp[8] from dp[4], and so on. A descending loop ensures every source state belongs to the earlier set of processed values rather than to a state created moments before.

Writing the algorithm in Python

The one-dimensional algorithm can be expressed with straightforward pseudocode:

create an array dp of target + 1 false values
dp[0] = true

for each number x:
    for sum from target down to x:
        dp[sum] = dp[sum] OR dp[sum - x]

return dp[target]

A Python implementation follows the same structure:

def subset_sum(values, target):
    if target < 0:
        return False

    reachable = [False] * (target + 1)
    reachable[0] = True

    for value in values:
        if value < 0:
            raise ValueError("This implementation expects non-negative values")

        for current_sum in range(target, value - 1, -1):
            reachable[current_sum] = (
                reachable[current_sum]
                or reachable[current_sum - value]
            )

    return reachable[target]

For a web-based calculator or teaching tool, this small routine could sit behind a form that accepts values and a target. A practical web development reference can help when connecting an algorithm like this to input validation, browser events, or a result display.

The early target < 0 check is useful because non-negative input values cannot create a negative total. The code also rejects negative values rather than silently applying a recurrence that does not support them. In production software, inputs might come from a CSV export, a budgeting spreadsheet, or a local retail inventory system, so validation deserves attention.

Tracing a worked example

Consider values = [3, 5, 7] and target = 10. Start with:

sum:       0     1     2     3     4     5     6     7     8     9    10
reachable T     F     F     F     F     F     F     F     F     F     F

After processing 3, sums 0 and 3 are reachable. Processing 5 adds 5 and 8, because 5 can stand alone and 3 + 5 = 8. The table now recognises 0, 3, 5, 8. When 7 is processed, it can create 7, 10, and other totals that fit within the target. Since 10 becomes true, the function returns True.

The descending update is visible in this example. When processing 5, the algorithm must use the state from before 5 was added. If the loop moved upwards, it could first create sum 5, then use that newly created state to create sum 10, which appears valid here but would represent using the same 5 twice. A different input could expose the error more clearly.

A useful debugging technique is to print the reachable sums after each item. This lets learners compare the program’s state with a manually calculated set. It is particularly effective when teaching the algorithm in Melbourne, Canberra, or online study groups where participants may have different levels of programming experience.

Analysing performance and limitations

With n input values and target T, the one-dimensional dynamic programming solution runs in O(nT) time and uses O(T) additional space. This is much better than checking all 2^n subsets when the target is moderate. It is called pseudo-polynomial because the running time depends on the numeric value of T, not only on the number of bits needed to encode it.

That distinction matters. A target of 50,000 may be practical, while a target of several billion is not, even if the input contains only a few values. A business system handling large Australian dollar amounts should usually convert dollars to cents carefully, then consider whether the resulting target makes a Boolean table sensible. Floating-point prices should not be placed directly into an index.

Bitsets can improve practical speed by representing reachable sums as bits and shifting the entire set for each value. In Python, an integer-based approach can be compact:

def subset_sum_bitset(values, target):
    reachable = 1

    for value in values:
        if value < 0:
            raise ValueError("Values must be non-negative")
        reachable |= reachable << value

    return bool((reachable >> target) & 1)

This version may use more efficient low-level operations, although it still has a pseudo-polynomial character. For geometric data or spatial queries, subset sum is not the right tool; a discussion of nearest-neighbour search illustrates why algorithm choice should follow the structure of the problem rather than the availability of a familiar technique.

Handling variants and edge cases

The empty input has a simple result: it can form target zero, but no positive target. Likewise, any target of zero is achievable by selecting no values, assuming the problem permits the empty subset. These cases should be covered by unit tests before testing larger examples.

Duplicate values are allowed and are treated as separate items. For instance, [4, 4] can form 8 because there are two copies. Zero values do not change reachability, though they may represent distinct selectable items in a reconstruction task. If negative numbers are permitted, the ordinary dp[0..target] design needs modification, such as an offset index or a set of reachable sums.

Sometimes the problem asks for the actual subset rather than a yes-or-no answer. Store a parent pointer, the item index that created each sum, or use a two-dimensional table. After reaching target, trace backwards to determine which values were selected. If the goal is to count subsets, minimise the number of items, or maximise a score under a capacity, the state and recurrence must be adapted rather than copied unchanged.

Australian applications can introduce additional constraints. A roster may need to match a number of hours, a parcel system in Perth may need to fill a capacity, and a school exercise may use whole marks rather than arbitrary decimals. Choosing an integer unit and stating whether each item can be used once are essential modelling decisions.

Practical checks before coding

Dynamic programming solutions are easiest to trust when the problem statement, state definition, and loop direction all agree. Use the following checks when implementing or reviewing a subset-sum routine:

Confirm that every input value is non-negative, or choose a design that supports negative values.
Decide whether each item may be selected once, multiple times, or not at all.
Initialise the zero sum as reachable before processing any values.
Iterate the one-dimensional table from the target down to the current value.
Convert decimal quantities into safe integer units such as cents before indexing.
Test empty input, target zero, an impossible target, duplicate values, and a target larger than every individual value.
Measure n and the target size before choosing a table, bitset, or another algorithm.

The most common bug is an upward loop in the one-dimensional implementation. The most common modelling mistake is confusing subset sum with unbounded coin change. Both errors can produce plausible results on small examples, so tests should include cases where reusing one value would change the answer.

For a compact educational implementation, the Boolean table is usually the clearest choice. For large targets, a bitset or a different formulation may be preferable. Good algorithm design balances correctness, memory use, input scale, and the exact output required by the application.