DSA

Subsets with sum k

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

August 8, 2026

DSA Dynamic Programming DP LeetCode Practice Backtracking Recursion

Given an array arr of non-negative integers and an integer target, the task is to count all subsets of the array whose sum is equal to the given target.

Practice Link

Recursive#

For each element at index idx we branch: skip it (same target, move to idx-1) or include it (reduce target by arr[idx], move to idx-1). We count subsets by returning 1 when the target reaches exactly 0 and 0 when we run out of elements. Because no results are cached, overlapping sub-problems are recomputed, yielding O(2^n) time.

cpp

class Solution{
	public:
    int MOD = 1e9+7;
    int perfectSumUtil(vector<int>&arr, int K, int idx){
        
        if(K==0)
            return 1;
            
        if(idx<0){
            return 0;
        }
        

        int not_take = perfectSumUtil(arr, K, idx-1);
        int take = 0;
        if(arr[idx] <= K)
            take = perfectSumUtil(arr, K - arr[idx], idx-1);

        return take + not_take;
    }

	int perfectSum(vector<int>&arr, int K){
        int n = arr.size();
        return perfectSumUtil(arr, K, n-1)%MOD;
	}
};

Time Complexity - O(2^n) -> TLE

Memoized#

Store results in memo[idx][K] — a 2D table indexed by the current element and remaining target. Each unique (idx, K) pair is computed exactly once, reducing time to O(n*k). The modular arithmetic prevents integer overflow when counts are large.

cpp

class Solution{
	public:
    int MOD = 1e9 + 7;
    int perfectSumUtil(vector<int>&arr, int K, int idx, vector<vector<int>> &memo){
        
        if(K==0)
            return 1;

        if(idx<0)
            return 0;

        if(memo[idx][K] != -1)
            return memo[idx][K];

        long long not_take = perfectSumUtil(arr, K, idx-1, memo);
        long long take = 0;
        if(arr[idx] <= K)
            take = perfectSumUtil(arr, K - arr[idx], idx-1, memo);

        return memo[idx][K] = (take + not_take)%MOD;
    }

	int perfectSum(vector<int>&arr, int K){
        int n = arr.size();
        vector<vector<int>> memo(n, vector<int>(K+1, -1)); 
        return perfectSumUtil(arr, K, n-1, memo);
	}
};

Time Complexity - O(n*k)

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

Tabulation#

dp[i][j] = number of subsets using elements from index 0 to i that sum to j. Initialize dp[i][0] = 1 for all rows (empty subset always achieves sum 0), and dp[0][arr[0]] = 1 for the first element. Fill the table row by row from i=1 to n-1: each cell combines "skip" (dp[i-1][j]) and "take" (dp[i-1][j - arr[i]]) counts. This eliminates the recursive stack and computes the answer at dp[n-1][K] in O(n*k) time and space.

cpp

class Solution{
	public:
    int MOD = 1e9 + 7;

	int perfectSum(vector<int>&arr, int K){
        int n = arr.size();

        // dp[i][j] -> number of subsets using elements from 0…i that sum to j
        vector<vector<int>> dp(n, vector<int>(K+1, 0));

        for(int i=0;i<n;i++){
            dp[i][0] = 1; //A sum of 0 is always possible
        }

        if(arr[0] <= K)
            dp[0][arr[0]] = 1; //one subset exists

        for(int i=1;i<n;i++){
            for(int j=1;j<=K;j++){
                long long not_take = dp[i-1][j];

                long long take = 0;
                if(arr[i] <= j)
                    take = dp[i-1][j-arr[i]];

                dp[i][j] = (take+not_take)%MOD;
            }
        }

        return dp[n-1][K];
	}
};

Time Complexity - O(n*k)

Space Complexity - O(n*k)

DSAPartition Equal Subset SumTabulation approach. Optimal — Time O(n*k), Space O(k).DSASubset Sum equal to targetCovers: Recursion, Memoized, Tabulation. 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

Recursive#

Memoized#

Tabulation#

Related articles