0/1 Knapsack Pattern: The DP Behind Subset Sum and Target Sum

You keep writing Subset Sum as a brand-new backtracking problem when it is just a 0/1 Knapsack where weights and values are the exact same numbers. The moment an interviewer drops a problem asking if an array adds up to a target, they are testing if you recognize the item-inclusion choice from the knapsack template. Stop treating every dynamic programming variation as a distinct puzzle to memorize.

The Family Tree of 0/1 Knapsack

Every variation in this family shares one core mechanic: at every index i, you either include the current element or you leave it out.

Subset Sum asks if you can pick a subset of [3, 34, 4, 12, 5, 2] to hit a target of 9. Your capacity is 9, and each number acts as both its own weight and its own value.

Partition Equal Subset Sum just hides the target inside the array sum. If [1, 5, 11, 5] adds up to 22, your target is 22 / 2, which means you need a subset sum of 11.

Target Sum adds a plus or minus sign to each number, turning it into a variation of counting subsets with a given difference.

Count Subsets with Given Difference splits the array into two subsets whose subtraction equals a target diff. If the total sum is sum, and the subset sums are s1 and s2, then s1 - s2 = diff and s1 + s2 = sum. Add those two equations and you get s1 = (sum + diff) / 2, which brings you right back to standard subset sum counting.

Tracing the State Transition

Let us trace Subset Sum for the array [2, 3, 5] and a target of 5 using a small table.

Rows represent the elements up to index i, and columns represent every possible sum from 0 to 5.

Sum:    0  1  2  3  4  5
{}      T  F  F  F  F  F
{2}     T  F  T  F  F  F
{2,3}   T  F  T  T  F  T
{2,3,5} T  F  T  T  T  T

At row 2 and column 5, the number 3 is less than or equal to the target sum 5. You look at the cell above it at column 5 - 3 = 2, which is T, or you look at the cell directly above at column 5, which is F. Since one option gives T, the new cell becomes T.

From Recursion to 1D Space

Your recursive solution starts with a function like solve(index, target) that branches into two calls.

Bool solve(int i, int target, vector<int>& arr) {
    If (target == 0) return true;
    If (i == 0) return arr[0] == target;
    Bool notTaken = solve(i - 1, target, arr);
    Bool taken = false;
    If (arr[i] <= target) {
        Taken = solve(i - 1, target - arr[i], arr);
    }
    Return notTaken || taken;
}

Memoization stores these states in a 2D array of size n by target + 1. That fixes the overlapping subproblems.

Table tabulation removes recursion overhead by filling the 2D grid iteratively.

Space optimization drops the first dimension entirely. Because row i only ever reads from row i - 1, you only need a single 1D array of size target + 1.

Walk the inner loop backwards from target down to arr[i] so you do not overwrite values you still need for the current row.

The Rule of Thumb

1. Identify the array element as both weight and value.
2. Set the table columns from 0 to target.
3. Iterate the inner loop backwards for 1D space.
4. Return dp[target] without hesitation.

Moving Forward

Open DSA Tracker today and solve Partition Equal Subset Sum without looking at the recurrence relation hint.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Dynamic programming on Wikipedia.