DSA

Subset Sum equal to target

Covers: Recursion, Memoized, Tabulation. Optimal — Time O(n*k), Space O(n*k ).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePracticeBacktrackingRecursion

Given an array of positive integers arr[] and a value target, determine if there is a subset of the given array with sum equal to given target.

Practice Link

Recursion Solution#

For each element at index idx, either skip it (keep the same target, move to idx-1) or include it (subtract from the target, move to idx-1). Return true when the target reaches 0 (found a valid subset), or false when indices are exhausted. Without caching, overlapping (idx, target) states cause O(2^n) time.

cpp
class Solution {
  public:
  
    bool isSubsetSumUtil(vector<int> &arr, int idx, int target)
    {
        if(target==0)
            return true;
        if(idx<0)
            return false;
        bool not_take = isSubsetSumUtil(arr, idx-1, target);
        bool take = false;
        if(arr[idx] <=target)
            take = isSubsetSumUtil(arr, idx-1, target-arr[idx]);
        return take || not_take;
    }
  
    bool isSubsetSum(vector<int>& arr, int target) {
        return isSubsetSumUtil(arr, arr.size()-1, target);
    }
};

Time Complexity - O(2^n)

Space Complexity - O(n)

Memoized Solution#

Cache results in memo[idx][target]. Each of the n × (k+1) states is solved once, reducing time to O(nk). The recursive call stack still adds O(n) overhead on top of the O(nk) memo table.

cpp
class Solution {
  public:
  
    bool isSubsetSumUtil(vector<int> &arr, int idx, int target, vector<vector<int>> &memo)
    {
        if(target==0)
            return true;
        if(idx<0)
            return false;
            
        if(memo[idx][target] != -1)
            return memo[idx][target];
        
        bool not_take = isSubsetSumUtil(arr, idx-1, target, memo);
        bool take = false;
        if(arr[idx] <=target)
            take = isSubsetSumUtil(arr, idx-1, target-arr[idx], memo);
        return memo[idx][target] = take || not_take;
    }
  
    bool isSubsetSum(vector<int>& arr, int target) {
        vector<vector<int>> memo(arr.size(), vector<int>(target+1, -1));
        return isSubsetSumUtil(arr, arr.size()-1, target, memo);
    }
};

Time Complexity - O(n*k)

Space Complexity - O(n*k ) + O(n)

Tabulation Solution#

Build dp[i][j] = true if a subset of elements 0..i sums to j. Initialize dp[i][0] = true for all rows (empty subset), and dp[0][arr[0]] = true for the first element alone. Fill row by row combining "skip" and "include". This eliminates the recursion stack, keeping O(nk) time and O(nk) space.

cpp
class Solution {
  public:
  
    bool isSubsetSum(vector<int>& arr, int target) {
        int n = arr.size();
        vector<vector<bool>> dp(n, vector<bool>(target+1, false));
        
        for(int i=0; i<n; i++)
            dp[i][0] = true;
        
        if(arr[0] <= target)
            dp[0][arr[0]] = true;
            
        for(int i=1; i<n; i++)
        {
            for(int j=1; j<=target; j++)
            {
                bool not_take = dp[i-1][j];
                bool take = false;
                if(arr[i] <= j)
                    take = dp[i-1][j-arr[i]];
                    
                dp[i][j] = take || not_take;
            }
        }
        
        
        return dp[n-1][target];
    }
};

Time Complexity - O(n*k)

Space Complexity - O(n*k )

Related articles

DSAPartition Equal Subset SumTabulation approach. Optimal — Time O(n*k), Space O(k).DSASubsets with sum kCovers: Recursive, Memoized. Optimal — Time O(n*k), Space O(n*k).DSAGenerate ParenthesesGenerate all combinations of well-formed parentheses using backtracking. Optimal — Time O(4ⁿ/√n), Space O(n).6 min read