DEV Community

Dolly Sharma
Dolly Sharma

Posted on

Subset Sum Equal to K — All Approaches (C++)

#algorithms #computerscience #cpp #tutorial

Subset Sum Equal to K — All Approaches (C++)

Subset Sum is a classic Dynamic Programming problem.

Problem

Given an array arr of n positive integers and a number k, determine whether there exists a subset whose sum equals k.

Example:

arr = [1,2,3,4]
k = 5
Enter fullscreen mode Exit fullscreen mode

Possible subset:

1 + 4 = 5
Enter fullscreen mode Exit fullscreen mode

Answer → true

1️⃣ Recursive Approach (Brute Force)

Idea:
For every element we have two choices:

  • Take the element
  • Do not take the element

Recurrence 

f(index, target)
Enter fullscreen mode Exit fullscreen mode

Base Cases 

if target == 0 → true
if index == 0 → arr[0] == target
Enter fullscreen mode Exit fullscreen mode

Code 

bool f(int ind, int target, vector<int>& arr){

    if(target == 0) return true;

    if(ind == 0)
        return arr[0] == target;

    bool notTake = f(ind-1, target, arr);

    bool take = false;
    if(arr[ind] <= target)
        take = f(ind-1, target-arr[ind], arr);

    return take || notTake;
}

bool subsetSumToK(int n, int k, vector<int>& arr){
    return f(n-1, k, arr);
}
Enter fullscreen mode Exit fullscreen mode

Complexity 

Time  : O(2^n)
Space : O(n)
Enter fullscreen mode Exit fullscreen mode

Very slow for large n.

2️⃣ Memoization (Top-Down DP)

Avoid recomputing the same states.

DP State 

dp[index][target]
Enter fullscreen mode Exit fullscreen mode

Code 

bool f(int ind, int target, vector<int>& arr, vector<vector<int>>& dp){

    if(target == 0) return true;

    if(ind == 0)
        return arr[0] == target;

    if(dp[ind][target] != -1)
        return dp[ind][target];

    bool notTake = f(ind-1, target, arr, dp);

    bool take = false;
    if(arr[ind] <= target)
        take = f(ind-1, target-arr[ind], arr, dp);

    return dp[ind][target] = take || notTake;
}

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<vector<int>> dp(n, vector<int>(k+1, -1));

    return f(n-1, k, arr, dp);
}
Enter fullscreen mode Exit fullscreen mode

Complexity 

Time  : O(n × k)
Space : O(n × k) + recursion stack
Enter fullscreen mode Exit fullscreen mode

3️⃣ Tabulation (Bottom-Up DP)

Build DP table iteratively.

DP Table 

dp[i][target]
Enter fullscreen mode Exit fullscreen mode

Meaning:

Using elements 0..i, can we form target?

Code 

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<vector<bool>> dp(n, vector<bool>(k+1,false));

    for(int i=0;i<n;i++)
        dp[i][0] = true;

    if(arr[0] <= k)
        dp[0][arr[0]] = true;

    for(int ind=1; ind<n; ind++){

        for(int target=1; target<=k; target++){

            bool notTake = dp[ind-1][target];

            bool take = false;
            if(arr[ind] <= target)
                take = dp[ind-1][target-arr[ind]];

            dp[ind][target] = take || notTake;
        }
    }

    return dp[n-1][k];
}
Enter fullscreen mode Exit fullscreen mode

Complexity 

Time  : O(n × k)
Space : O(n × k)
Enter fullscreen mode Exit fullscreen mode

4️⃣ Space Optimized DP

Observation:

Each row only depends on the previous row.

So we can reduce space to O(k).

Code 

bool subsetSumToK(int n, int k, vector<int>& arr){

    vector<bool> prev(k+1,false);

    prev[0] = true;

    if(arr[0] <= k)
        prev[arr[0]] = true;

    for(int ind=1; ind<n; ind++){

        vector<bool> cur(k+1,false);
        cur[0] = true;

        for(int target=1; target<=k; target++){

            bool notTake = prev[target];

            bool take = false;
            if(arr[ind] <= target)
                take = prev[target-arr[ind]];

            cur[target] = take || notTake;
        }

        prev = cur;
    }

    return prev[k];
}
Enter fullscreen mode Exit fullscreen mode

Complexity 

Time  : O(n × k)
Space : O(k)
Enter fullscreen mode Exit fullscreen mode

Key DP Pattern

This pattern is used in many problems:

Problem Concept
Partition Equal Subset Sum Subset Sum
Target Sum Subset Count
Minimum Subset Difference Partition DP
Count Subsets with Sum K Variation

Summary

Approach Time Space
Recursion O(2^n) O(n)
Memoization O(n×k) O(n×k)
Tabulation O(n×k) O(n×k)
Space Optimized O(n×k) O(k)

Top comments (0)