Dynamic Programming (DP 17): Counts Subsets with Sum $K$ (DP on Subsequences)

1. Problem Statement & Context

This chapter extends our exploration of dynamic programming on subsequences. In preceding lessons (DP 14 through DP 16), we investigated Subset Sum problems, which asked a boolean question: "Does there exist at least one subset whose elements sum up to a given target $K$?"

Here, the problem transforms from existence to counting:

Problem Definition: Given a 0-indexed array of positive integers and a target number $K$, count the total number of distinct subsets (or subsequences) whose elements sum up to exactly $K$.

Key Distinction: Distinct Subsets vs. Identical Elements

Consider an array:

nums = [1, 2, 2, 3], target = 3

Valid subsets that yield a sum of $3$:

1. Choosing index 0 (value 1) and index 1 (value 2). Sum: 1 + 2 = 3.
2. Choosing index 0 (value 1) and index 2 (value 2). Sum: 1 + 2 = 3. (Note: Although the subset values look identical [1, 2], they originate from different physical indices, making them distinct subsequences).
3. Choosing index 3 (value 3). Sum: 3.

Total Count: 3 valid subsets.

2. Prerequisites & Core Mental Model

Before tackling DP 17, ensure you are comfortable with:

• DP 14: The foundational pick/not-pick technique for subsequences.
• Recursion Lecture 7: The philosophy of counting problems in recursion.

Golden Rules for Counting Recursion

1. Express in Indexes & Target: The state function will track the current array index and the remaining target sum: f(index, sum).
2. Explore All Choices: At every step, we evaluate two exclusive choices: Not-Pick the current element or Pick the current element.
3. Sum Up Choices: Since we need the total count of valid subsets, the result for any state is the sum of choices:

4. Base Case Return Values:
   • If a valid configuration or target condition is met, return 1.
   • If the path fails or exceeds constraints, return 0.

3. Step-by-Step Recursive Evolution

Let's construct the recurrence relation f(index, sum) representing: "Number of valid subsequences from index 0 to index that sum up to sum."

Choice 1: Not-Pick

If we decide not to include nums[index] in our subset:

• The required sum remains unchanged.
• We move to the previous index: f(index - 1, sum).

Choice 2: Pick

Can we always pick the current element? Only if the element is less than or equal to the remaining sum. If nums[index] > sum, picking it would overshoot our target, rendering that path invalid (contributing 0 ways).

• If nums[index] <= sum, we can pick it.
• The remaining target is reduced by nums[index].
• We move to the previous index: f(index - 1, sum - nums[index]).

Complete Recurrence Equation

4. Refining Base Cases

When our recursion reaches index == 0, we are left with a single element (nums[0]). How do we evaluate whether it forms a valid subset?

Handling Zero Sums and Exact Matches

1. If sum == 0: Even if we are at index 0, achieving a sum of 0 is always possible by taking an empty subset (or not picking the remaining elements). Thus, it contributes 1 way.
2. Exact Element Match: If sum == nums[0], we can pick this single element to match the remaining sum, contributing 1 way. Otherwise, it contributes 0 ways.

Note on Edge Cases with Zeros: If the array contains zeros, a sum of 0 can match in multiple ways. For standard positive-integer arrays without zeros, our base case simplifies cleanly to checking if nums[0] == sum (returning 1 or 0), alongside handling sum == 0.

5. Complete Recursive Solution & Complexity

Recursive Code Structure

int countWays(int index, int sum, vector<int>& nums) {
    if (sum == 0) return 1;
    if (index == 0) {
        return (nums[0] == sum) ? 1 : 0;
    }
    
    int notPick = countWays(index - 1, sum, nums);
    int pick = 0;
    if (nums[index] <= sum) {
        pick = countWays(index - 1, sum - nums[index], nums);
    }
    
    return notPick + pick;
}

Complexity Analysis

• Time Complexity: $O(2^n)$ because at every index, we branch into 2 choices (pick and not pick).
• Space Complexity: $O(n)$ auxiliary stack space due to recursive function calls.

6. Memoization (Top-Down DP)

Since overlapping subproblems occur repeatedly across different branches, we memoize states using a 2D table of size [N][Target + 1].

Memoization Implementation

int countWaysUtil(int index, int sum, vector<int>& nums, vector<vector<int>>& dp) {
    if (sum == 0) return 1;
    if (index == 0) {
        return (nums[0] == sum) ? 1 : 0;
    }
    
    if (dp[index][sum] != -1) return dp[index][sum];
    
    int notPick = countWaysUtil(index - 1, sum, nums, dp);
    int pick = 0;
    if (nums[index] <= sum) {
        pick = countWaysUtil(index - 1, sum - nums[index], nums, dp);
    }
    
    return dp[index][sum] = notPick + pick;
}

int findWays(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(target + 1, -1));
    return countWaysUtil(n - 1, target, nums, dp);
}

Memoized Complexities

• Time Complexity: $O(N \times \text{Target})$
• Space Complexity: $O(N \times \text{Target})$ for the DP table $+ O(N)$ auxiliary stack space.

7. Tabulation (Bottom-Up DP)

To eliminate stack overflow risks and recursion overhead, we convert the top-down memoization into a bottom-up iterative tabulation approach.

Tabulation Translation Rules

1. Initialize a 2D DP table: vector<vector<int>> dp(n, vector<int>(target + 1, 0)).
2. Set up base cases:
   • For any index, a target sum of 0 has 1 way (empty subset).
   • At index = 0, dp[0][nums[0]] = 1 (provided nums[0] <= target).
3. Run nested loops for index (from 1 to n - 1) and sum (from 0 to target).
4. Copy the transition logic.

Tabulation Code

int findWays(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(target + 1, 0));
    
    // Base case 1: sum = 0 is always possible (1 way)
    for (int i = 0; i < n; i++) {
        dp[i][0] = 1;
    }
    
    // Base case 2: for the first element
    if (nums[0] <= target) {
        dp[0][nums[0]] = 1;
    }
    
    // Fill the DP table iteratively
    for (int index = 1; index < n; index++) {
        for (int sum = 0; sum <= target; sum++) {
            int notPick = dp[index - 1][sum];
            int pick = 0;
            if (nums[index] <= sum) {
                pick = dp[index - 1][sum - nums[index]];
            }
            dp[index][sum] = notPick + pick;
        }
    }
    
    return dp[n - 1][target];
}

8. Space Optimization

Notice that computing the index row in our tabulation only requires values from the immediate previous row (index - 1). We can optimize our memory footprint from $O(N \times \text{Target})$ down to $O(\text{Target})$ using two 1D arrays: prev and cur.

Space-Optimized Implementation

int findWays(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> prev(target + 1, 0), cur(target + 1, 0);
    
    // Base cases
    prev[0] = 1;
    if (nums[0] <= target) {
        prev[nums[0]] = 1;
    }
    
    for (int index = 1; index < n; index++) {
        for (int sum = 0; sum <= target; sum++) {
            int notPick = prev[sum];
            int pick = 0;
            if (nums[index] <= sum) {
                pick = prev[sum - nums[index]];
            }
            cur[sum] = notPick + pick;
        }
        prev = cur;
    }
    
    return prev[target];
}

Optimized Complexities

• Time Complexity: $O(N \times \text{Target})$
• Space Complexity: $O(\text{Target})$

9. Handling Negative Numbers (Discussion & Challenge)

A common interview follow-up question: "What if the array contains negative integers?"

In standard subset-sum or count-subset problems with negative numbers, standard 2D arrays fail because negative sums shift indices out of bounds (e.g., trying to access dp[index][-5]).

Challenge Question: If the array contains negative numbers and sums can drop below zero, which alternative data structures (such as Hash Maps or Offset-shifted arrays) can store states of (index, sum), and how does it impact time complexity? (Share your thoughts in the comments!)

10. Summary and Key Takeaways

• Problem Core: Counting subsets matching target $K$ uses the exact same pick vs. not-pick backbone as boolean subset sum, with addition replacing logical OR.
• Base Cases: A target sum of 0 always yields 1 way; base elements must match the target directly.
• Recurrence Relationship:

• Memoization Strategy: A 2D table dp[n][target + 1] eliminates redundant calculations, reducing time complexity from exponential $O(2^n)$ to pseudo-polynomial $O(N \times \text{Target})$.
• Tabulation Evolution: Bottom-up iteration replaces recursion, removing stack overhead.
• Space Optimization: Since each row depends only on the previous row, space complexity drops from $O(N \times \text{Target})$ to a lean $O(\text{Target})$.