Subset Sum Problem | Solved using Dynamic Programming

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

Here’s the [Problem Link] to begin with.

Examples:

Input: arr[] = [3, 34, 4, 12, 5, 2], sum = 9
Output: true 
Explanation: Here there exists a subset with target sum = 9, 4+3+2 = 9.

Input: arr[] = [3, 34, 4, 12, 5, 2], sum = 30
Output: false
Explanation: There is no subset with target sum 30.

Input: arr[] = [1, 2, 3], sum = 6
Output: true
Explanation: The entire array can be taken as a subset, giving 1 + 2 + 3 = 6.

Constraints:
1 <= arr.size() <= 200
1<= arr[i] <= 200
1<= sum <= 10⁴

Solution 1: Recursion (Brute Force)

Intuition and Approach

At each index, you decide to include the current element (if it doesn’t exceed target) or exclude it. This forms a binary decision tree. Base cases:

• If target == 0 → True (empty subset achieves 0).
• If index == 0 → True only if arr equals target.
  This explores all subsets but with exponential time due to overlapping subproblems.

Code Implementation

class Solution:
    def solve(self, index, target, arr):
        # Base: target achieved
        if target == 0:
            return True
        # Base: only first element available
        if index == 0:
            if arr == target:
                return True
            return False
        # Choice: pick only if feasible
        if arr[index] > target:
            pick = False
        else:
            pick = self.solve(index - 1, target - arr[index], arr)
        # Choice: not pick current element
        not_pick = self.solve(index - 1, target, arr)
        # Return if any choice leads to True
        return pick or not_pick

    def isSubsetSum(self, arr, sum):
        n = len(arr)
        # Start from the last index aiming for target sum
        return self.solve(n - 1, sum, arr)

Code Explanation

• The function solve(index, target) tries both decisions: include arr[index] (if allowed) or exclude it.
• If target hits 0 at any depth, it signals a valid subset.
• The first-element base case avoids negative indices and settles the smallest subproblem.

Time and Space Complexity

• Precise: Time O(2^n), as each element can be picked or not; Space O(n) recursion depth.
• Simplified: Exponential time, linear stack space.

Conclusion

Good for intuition and very small inputs, but inefficient due to repeated subproblems.

Solution 2: Memoization (Top-Down DP)

Intuition and Approach

The same (index, target) states recur many times. Cache results in a 2D table dp[index][target]:

• Before computing, return cached dp if already set.
• Otherwise, compute pick/not-pick as recursion and store True/False.

Code Implementation

class Solution:
    def solve(self, index, target, arr, dp):
        # If target achieved
        if target == 0:
            return True
        # If only first element can be used
        if index == 0:
            if arr[0] == target:
                return True
            return False
        # Use memoized result if available
        if dp[index][target] != -1:
            return dp[index][target]
        # Try picking current element if feasible
        if arr[index] > target:
            pick = False
        else:
            pick = self.solve(index - 1, target - arr[index], arr, dp)
        # Or skip current element
        not_pick = self.solve(index - 1, target, arr, dp)
        # Store boolean result in dp
        return pick or not_pick

    def isSubsetSum(self, arr, sum):
        n = len(arr)
        # dp[index][target] = -1 (unknown), else True/False
        dp = [[-1 for _ in range(sum + 1)] for _ in range(n)]
        return self.solve(n - 1, sum, arr, dp)

Code Explanation

• dp[index][target] caches whether a subset of arr[0..index] can form target.
• Converts exponential recursion into polynomial by avoiding recomputation of identical states.

Time and Space Complexity

• Precise: Time O(n * sum), Space O(n * sum) for dp + O(n) stack.
• Simplified: Pseudo-polynomial in target, linear stack.

Conclusion

Efficient and interview-ready; ideal when sum is not too large.

Solution 3: Tabulation (Bottom-Up DP)

Intuition and Approach

Build a boolean table dp[n][sum+1] where dp[i][t] indicates if you can make sum t using arr[0..i].

• Initialize dp[i] = True for all i (target 0 is always achievable).
• Initialize dp[arr] = True if it doesn’t exceed sum.
• Transition:
  • If arr[i] > t → pick = False else pick = dp[i-1][t – arr[i]]
  • not_pick = dp[i-1][t]
  • dp[i][t] = pick or not_pick

Code Implementation

class Solution:
    def isSubsetSum(self, arr, sum):
        n = len(arr)
        # dp[i][t] -> can we make sum t using first i elements (0..i)?
        dp = [[False for _ in range(sum + 1)] for _ in range(n)]
        # Sum 0 achievable by picking empty subset
        for index in range(n):
            dp[index] = True
        # Handle first element
        if arr <= sum:
            dp[arr] = True
        # Fill table for remaining elements
        for index in range(1, n):
            for target in range(0, sum + 1):
                if arr[index] > target:
                    pick = False
                else:
                    pick = dp[index - 1][target - arr[index]]
                not_pick = dp[index - 1][target]
                dp[index][target] = pick or not_pick
        # Final answer: can we form 'sum' using all elements?
        return dp[n - 1][sum]

Code Explanation

• Iteratively fills achievable sums per prefix of the array.
• Each state depends only on the previous row, enabling further space optimization.

Time and Space Complexity

• Precise: Time O(n * sum), Space O(n * sum).
• Simplified: Pseudo-polynomial time/space.

Conclusion

Deterministic and easy to debug; preferred when memory is acceptable.

Solution 4: Tabulation (Space Optimization)

Intuition and Approach

Current dp row depends only on the previous row, so we can roll arrays:

• Maintain prev (for i-1) and curr (for i).
• After computing curr for all targets, assign prev = curr.

Code Implementation

class Solution:
    def isSubsetSum(self, arr, sum):
        n = len(arr)
        # prev[t] -> achievable with elements up to previous index
        prev = [False for _ in range(sum + 1)]
        prev = True  # sum 0 is always achievable
        if arr <= sum:
            prev[arr] = True
        # Iterate elements
        for index in range(1, n):
            curr = [False for _ in range(sum + 1)]
            for target in range(0, sum + 1):
                if arr[index] > target:
                    pick = False
                else:
                    pick = prev[target - arr[index]]
                not_pick = prev[target]
                curr[target] = pick or not_pick
            # Move window
            prev = curr
        return prev[sum]

Code Explanation

• Uses two 1D arrays to track reachable sums, preserving correctness with O(sum) space.
• Same transitions as full table but memory efficient.

Time and Space Complexity

• Precise: Time O(n * sum), Space O(sum).
• Simplified: Pseudo-polynomial time, linear space in target.

Conclusion

Best practical version for large n with moderate target sum; commonly expected in interviews.

Final Notes

• All approaches rely on the fundamental pick/not-pick decision per element.
• Base cases ensure correctness: reaching target 0 is always True; the single-item check at index 0 anchors recursion/DP.
• Memoization and tabulation both achieve O(n * sum) time; the space-optimized tabulation reduces memory to O(sum).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.