Target Sum Problem in C++ | Full DSA

 

🎯 Target Sum Problem in C++ | Full Breakdown from Striver’s DSA Lecture

🧩 Problem Statement 

You're given:

  • An array arr of integers.

  • A target sum T.

You must count how many subsets of arr add up exactly to the value T.

Example:


Input: arr = {1, 2, 3, 3}, target = 6
Output: 3

Why?
There are 3 subsets of arr that sum to 6:

  • {1, 2, 3}

  • {3, 3}

  • {1, 2, 3} again (from different indexes)

Each subset is valid even if the same value is reused from different positions (e.g., two different 3s).

❌ Brute Force Isn't Good Enough

Brute-force idea:

Try all 2ⁿ possible subsets, check if each subset sums to T.

Why this fails?

  • Time complexity is O(2ⁿ).

  • With n = 20, you already check over 1 million subsets.

  • Inefficient when array size grows.

✅ Dynamic Programming (DP) to the Rescue

We want a smarter way to find the count of valid subsets using memoization.

🧠 Core DP Concept

We use a 2D DP table to track possibilities:


dp[i][j] = number of subsets using first i elements that sum to j

Initialization:

  • dp[0][0] = 1:
    One way to reach sum 0 with 0 elements (the empty subset).

  • dp[0][j] = 0 for all j > 0:
    No way to form a positive sum using 0 elements.

🔁 Recurrence Relation (DP Transition)

For each element arr[i-1], we have two choices:

  1. Exclude the element
    → dp[i][j] = dp[i-1][j]

  2. Include the element (only if j >= arr[i-1])
    → dp[i][j] += dp[i-1][j - arr[i-1]]


if (j >= arr[i-1])
    dp[i][j] += dp[i-1][j - arr[i-1]];

Visual Concept (for each cell dp[i][j]):

Imagine filling a table row-by-row:

  • Take the value from above (exclude).

  • Optionally add value from top-left (include) if current element can be part of the subset.

💻 C++ Code (with Comments)


int countSubsets(vector<int>& arr, int T) {
    int n = arr.size();
    
    // Create a DP table with (n+1) rows and (T+1) columns, all 0 initially
    vector<vector<int>> dp(n+1, vector<int>(T+1, 0));
    
    // Base case: Only 1 way to make sum = 0 (pick nothing)
    dp[0][0] = 1;

    // Build the table
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= T; j++) {
            // Exclude current element
            dp[i][j] = dp[i-1][j];
            
            // Include current element if possible
            if (j >= arr[i-1])
                dp[i][j] += dp[i-1][j - arr[i-1]];
        }
    }

    // Final answer: how many subsets from all n elements give sum T
    return dp[n][T];
}

⏱️ Time & Space Complexity

  • Time: O(n × T)
    You compute each cell of the DP table once.

  • Space: O(n × T)
    Can be optimized to O(T) using a rolling 1D array.

🔬 Real-World Applications

  • 🎁 Finance: Pick a set of items whose total cost equals a budget.

  • 🧠 AI/ML: Select feature subsets that meet a scoring threshold.

  • 🎮 Games: Combine resources to hit an exact value.

⚠️ Common Mistakes to Avoid

  • Don’t forget dp[0][0] = 1. This initializes the DP base correctly.

  • Always check bounds:
    Only add dp[i-1][j - arr[i-1]] if j >= arr[i-1]

  • If large outputs are possible, use:

    • long long instead of int

    • Or add a mod (e.g., 1e9 + 7) to keep numbers within range

🧠 Tip: 1D Space Optimization

You can reduce space from O(n×T) to O(T) using a 1D array and reversing the inner loop:


vector<int> dp(T + 1, 0);
dp[0] = 1;

for (int num : arr) {
    for (int j = T; j >= num; j--) {
        dp[j] += dp[j - num];
    }
}
return dp[T];

Comments

Post a Comment