DP 14: Subset Sum Equals to Target | Dynamic Programming on Subsequences

This comprehensive guide explores the foundational pattern of Dynamic Programming on Subsequences and Subsets, specifically focusing on the canonical problem: Subset Sum Equals to Target.

1. Why Do We Need This? (The Subsequence & Target Paradigm)

Before tackling individual algorithms, we must understand the shift in our state representation from previous patterns:

• Previous Patterns (DP on Grids): We navigated 2D grid coordinates (i, j) from a start cell to an end cell.
• New Pattern (DP on Subsequences): We deal with subsequences or subsets, paired with a specific target value that we need to reach or verify.

Defining Subsequences vs. Subarrays

• Subsequence / Subset: Any contiguous or non-contiguous part of an array that maintains the relative order of elements.
• Rule of Order: If an array is [1, 3, 2], then [1, 2] is a valid subsequence because 1 appears before 2 in the original array, even though they are non-contiguous. However, [2, 1] is not a valid subsequence because it violates the original order.

2. Core Mental Model: The Two-Parameter State

When solving subsequence and target problems, your brain should immediately lock onto two core parameters:

1. The Array Index: Tracks our current position in the array.
2. The Target: Tracks the remaining sum we need to accumulate.

The Universal Recurrence Definition

Whenever we write a recursive function for subsequence problems, the function signature typically represents:

"In the entire array from index 0 to index, does there exist a subsequence that can form the given target?"

Expressed as a recurrence function:

f(index, target)

For an array of size $N$, we initiate our search from the very last element down to the first element: f(n - 1, target).

3. The 3-Step Master Recipe for Subsequence DP

Every Dynamic Programming problem on subsequences follows a rigid, repeatable 3-step blueprint:

1. Express everything in terms of (index, target): Define what the parameters mean.
2. Explore all possibilities at the current index: Decide what choices can be made.
3. Return the appropriate boolean combination: Combine choices using logical operators (OR for existence checks, SUM for counting ways).

Exploring Possibilities at an Index

When standing at a given index, you only ever have two fundamental choices:

1. Take the element: Include arr[index] in your subsequence. This reduces your remaining target by arr[index] and moves to index - 1.
2. Not take the element: Exclude arr[index] from your subsequence. Your target remains unchanged, but you still move to index - 1.

4. Naive Recursion: Base Cases and Recurrence Logic

To write the recursive solution, we must define bulletproof base cases.

Base Case 1: Target Reached ($0$)

If at any point our target becomes 0, it means we have successfully found a valid subset of elements summing up to the original target. We immediately return true.

Base Case 2: Reached the Beginning of the Array (index == 0)

If we have recursed all the way down to index == 0, our only remaining option is to check if our single remaining element matches the remaining target. We return true if arr[0] == target, else false.

Naive Recursive Implementation (Java / C++ conceptual)

bool f(int index, int target, vector<int>& arr) {
    // Base Case 1: Target achieved
    if (target == 0) return true;
    
    // Base Case 2: Reached the 0th index
    if (index == 0) return (arr[0] == target);
    
    // Choice 1: Exclude current element
    bool notTake = f(index - 1, target, arr);
    
    // Choice 2: Include current element (only if element <= target)
    bool take = false;
    if (target >= arr[index]) {
        take = f(index - 1, target - arr[index], arr);
    }
    
    // Return true if either choice succeeds
    return take || notTake;
}

• Time Complexity: $O(2^n)$ because at every index we branch into 2 recursive calls (Take / Not Take).
• Space Complexity: $O(n)$ auxiliary stack space.

5. Memoization (Top-Down DP)

Since overlapping subproblems exist (the same (index, target) state is reached via different execution paths), we can cache our results using a 2D DP table.

State Dimensions

• Index: Ranges from 0 to n - 1 (Size: n).
• Target: Ranges from 0 to k (Size: k + 1).
• DP Table Type: vector<vector<int>> dp(n, vector<int>(k + 1, -1))

Memoized Code Structure

bool f(int index, int target, vector<int>& arr, vector<vector<int>>& dp) {
    if (target == 0) return true;
    if (index == 0) return (arr[0] == target);
    
    if (dp[index][target] != -1) return dp[index][target];
    
    bool notTake = f(index - 1, target, arr, dp);
    bool take = false;
    if (target >= arr[index]) {
        take = f(index - 1, target - arr[index], arr, dp);
    }
    
    return dp[index][target] = (take || notTake);
}

• Time Complexity: $O(n \times k)$
• Space Complexity: $O(n \times k)$ for the DP table + $O(n)$ auxiliary recursion stack space.

6. Tabulation (Bottom-Up DP)

To eliminate auxiliary stack space entirely, we convert the top-down memoized solution into a bottom-up iterative table.

Step-by-Step Tabulation Conversion

1. Declare a 2D DP Table: vector<vector<bool>> dp(n, vector<bool>(k + 1, false))
2. Initialize Base Cases:
   • For any index, if target == 0, the answer is true. (dp[i][0] = true for all i).
   • For index 0, if arr[0] <= k, then dp[0][arr[0]] = true.
3. Populate Nested Loops:
   • Outer loop iterates through index from 1 to n - 1.
   • Inner loop iterates through target from 1 to k.

Tabulation Implementation

bool subsetSumToK(int n, int k, vector<int>& arr) {
    vector<vector<bool>> dp(n, vector<bool>(k + 1, false));
    
    // Base Case 1: Target 0 is always possible for any prefix of array
    for (int i = 0; i < n; i++) {
        dp[i][0] = true;
    }
    
    // Base Case 2: At index 0, we can form target equal to arr[0] (if within limit k)
    if (arr[0] <= k) {
        dp[0][arr[0]] = true;
    }
    
    // Fill the DP table bottom-up
    for (int index = 1; index < n; index++) {
        for (int target = 1; target <= k; target++) {
            bool notTake = dp[index - 1][target];
            bool take = false;
            if (target >= arr[index]) {
                take = dp[index - 1][target - arr[index]];
            }
            dp[index][target] = (take || notTake);
        }
    }
    
    return dp[n - 1][k];
}

7. Space Optimization (Reducing to $O(k)$)

Notice in our tabulation recurrence that to compute the current row (index), we only ever look back at the immediately previous row (index - 1). We never need rows older than index - 1.

The Two-Row Strategy

Instead of maintaining a full $N \times K$ matrix, we can maintain just two 1oggling rows:

• prev: Represents row index - 1
• curr: Represents row index

Space-Optimized Code

bool subsetSumToK(int n, int k, vector<int>& arr) {
    vector<bool> prev(k + 1, false), curr(k + 1, false);
    
    // Base Case initializations
    prev[0] = curr[0] = true;
    if (arr[0] <= k) {
        prev[arr[0]] = true;
    }
    
    for (int index = 1; index < n; index++) {
        for (int target = 1; target <= k; target++) {
            bool notTake = prev[target];
            bool take = false;
            if (target >= arr[index]) {
                take = prev[target - arr[index]];
            }
            curr[target] = (take || notTake);
        }
        prev = curr; // Shift rows forward
    }
    
    return prev[k];
}

8. Summary and Key Takeaways

• Subsequence Definition: Any contiguous or non-contiguous subset of array elements that strictly preserves the original index ordering.
• Two-State Parameters: Subsequence DP problems universally revolve around (index, target).
• The Core Binary Choice: At every index, evaluate take (if target >= arr[index]) and notTake, combining results with a logical || operator.
• Base Case Priority: Always define base cases for target exhaustion (target == 0) before boundary index checks.
• Space Optimization Rule: Whenever a recurrence state only depends on index - 1, the 2D DP matrix can be compressed into two 1D arrays (prev and curr), reducing space complexity from $O(N \times K)$ down to $O(K)$.