Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Subset Sum Equal to Target

HARDProblemSolveExternal Links

Description

Given an array of positive integers arr[] and a target value sum, determine whether there exists a subset of arr[] whose elements add up exactly to the given sum.

A subset can include any combination of elements from the array (including the empty set, which has sum 0, or the entire array). Each element can be used at most once.

Return true if such a subset exists, otherwise return false.

Examples

Example 1

Input: arr = [3, 34, 4, 12, 5, 2], sum = 9

Output: true

Explanation: The subset {4, 5} sums to 4 + 5 = 9, which equals the target. Another valid subset is {3, 4, 2} = 9. At least one exists, so we return true.

Example 2

Input: arr = [3, 34, 4, 12, 5, 2], sum = 30

Output: false

Explanation: No combination of elements from the array adds up to 30. The total sum of all elements is 3 + 34 + 4 + 12 + 5 + 2 = 60, so 30 is within range, but no specific subset achieves it.

Example 3

Input: arr = [1, 2, 3], sum = 6

Output: true

Explanation: The entire array is a valid subset: 1 + 2 + 3 = 6.

Constraints

  • 1 ≤ arr.size() ≤ 200
  • 1 ≤ arr[i] ≤ 200
  • 1 ≤ sum ≤ 10^4

Editorial

Brute Force - Recursion

Intuition

For every element in the array, we have exactly two choices: include it in our subset or exclude it. If we try all possible combinations of include/exclude decisions, we will eventually examine every possible subset.

We define a recursive function solve(n, target) that answers: "Using only the first n elements of the array, can we form a subset that sums to target?"

The recurrence is:

  • If target == 0, return true — the empty subset (or whatever we've already selected) sums to the target.
  • If n == 0 and target > 0, return false — no elements left but we haven't hit the target.
  • If arr[n-1] > target, we cannot include this element (it would overshoot), so we skip it: solve(n-1, target).
  • Otherwise, we try both: solve(n-1, target) (exclude) OR solve(n-1, target - arr[n-1]) (include).

The answer is solve(arr.size(), sum).

Step-by-Step Explanation

Let's trace with arr = [3, 34, 4, 12, 5, 2], sum = 9:

Step 1: Call solve(6, 9). We consider all 6 elements, target is 9. Last element is arr[5]=2. Branch into: exclude 2 → solve(5, 9) and include 2 → solve(5, 7).

Step 2: Explore solve(5, 9) first. Last element arr[4]=5. Branch: exclude 5 → solve(4, 9) and include 5 → solve(4, 4).

Step 3: Explore solve(4, 9). arr[3]=12 > 9, forced to exclude → solve(3, 9). arr[2]=4 ≤ 9, branch again. Eventually this entire subtree leads to dead ends.

Step 4: Deep in the tree: solve(2, 5) → solve(1, 5) → arr[0]=3 ≤ 5, so try include: solve(0, 2) = false (n=0, target>0). Try exclude: solve(0, 5) = false. Dead end!

Step 5: solve(4, 9) = false. The "exclude 5" path completely fails — we cannot reach sum 9 from {3, 34, 4, 12} alone.

Step 6: Backtrack. Now try solve(4, 4) — the "include 5" path. New target = 9 - 5 = 4. arr[3]=12 > 4, skip → solve(3, 4).

Step 7: solve(3, 4): Try include arr[2]=4 → solve(2, 0). Target drops to 4 - 4 = 0!

Step 8: solve(2, 0): target == 0 → return true! We found a valid subset: we included arr[4]=5 and arr[2]=4, giving {4, 5} = 9.

Step 9: Propagate true upward: solve(3, 4) = true → solve(4, 4) = true → solve(5, 9) = true → solve(6, 9) = true.

Brute Force Recursion — Include or Exclude Each Element — Watch the recursion tree branch at each element with two choices: include or exclude. Failed paths return false; the successful path finds subset {4, 5} = 9.

Algorithm

  1. Define solve(n, target) — returns true if a subset of arr[0..n-1] sums to target
  2. Base cases:
    • target == 0 → return true (empty subset)
    • n == 0 and target > 0 → return false (no elements left)
  3. If arr[n-1] > target, the element is too large to include → solve(n-1, target)
  4. Otherwise, return solve(n-1, target) OR solve(n-1, target - arr[n-1])
  5. Answer: solve(arr.size(), sum)

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(vector<int>& arr, int n, int target) {
        if (target == 0) return true;
        if (n == 0) return false;

        if (arr[n - 1] > target)
            return solve(arr, n - 1, target);

        return solve(arr, n - 1, target)
            || solve(arr, n - 1, target - arr[n - 1]);
    }

    bool isSubsetSum(vector<int>& arr, int sum) {
        return solve(arr, arr.size(), sum);
    }
};
class Solution:
    def isSubsetSum(self, arr: list[int], target: int) -> bool:
        def solve(n, target):
            if target == 0:
                return True
            if n == 0:
                return False

            if arr[n - 1] > target:
                return solve(n - 1, target)

            return (solve(n - 1, target)
                    or solve(n - 1, target - arr[n - 1]))

        return solve(len(arr), target)
class Solution {
    boolean solve(int[] arr, int n, int target) {
        if (target == 0) return true;
        if (n == 0) return false;

        if (arr[n - 1] > target)
            return solve(arr, n - 1, target);

        return solve(arr, n - 1, target)
            || solve(arr, n - 1, target - arr[n - 1]);
    }

    public boolean isSubsetSum(int[] arr, int sum) {
        return solve(arr, arr.length, sum);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, every element gives us two branches (include or exclude). The recursion tree has depth n and branching factor 2, yielding up to 2^n leaf nodes. For n = 200, this is astronomically large.

Space Complexity: O(n)

The recursion stack has depth at most n (one frame per element). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force generates up to 2^n recursive calls, which is exponential. With n up to 200, this means up to 2^200 ≈ 1.6 × 10^60 calls — far beyond any time limit.

The core issue is overlapping subproblems. Many different paths through the recursion tree lead to the same (n, target) state. For example, excluding element A then including element B might give the same (remaining_elements, remaining_sum) as including A then excluding B.

The state space is actually quite small: there are at most n × sum = 200 × 10,000 = 2,000,000 unique (n, target) pairs. If we store the result for each pair the first time it is computed, subsequent lookups become O(1). This is dynamic programming, and it reduces time from exponential to O(n × sum).

Bar chart comparing brute force O(2^n) versus DP O(n times sum). For n=200, sum=10000: brute force is off-chart while DP is 2 million operations.
Bar chart comparing brute force O(2^n) versus DP O(n times sum). For n=200, sum=10000: brute force is off-chart while DP is 2 million operations.

Better Approach - Tabulation (Bottom-Up DP)

Intuition

Instead of recursion, we build a 2D boolean table dp[i][j] where dp[i][j] = true means: "Using only the first i elements of the array, we can form a subset that sums to exactly j."

We fill this table row by row (one element at a time) and column by column (from sum 0 up to the target). For each cell, the logic mirrors the recurrence:

  • If arr[i-1] > j, the current element is too heavy to include → dp[i][j] = dp[i-1][j]
  • Otherwise, we can include or exclude it → dp[i][j] = dp[i-1][j] OR dp[i-1][j - arr[i-1]]

The base cases are: dp[i][0] = true for all i (sum 0 is always achievable with an empty subset) and dp[0][j] = false for j > 0 (no elements means no positive sums).

The answer is dp[n][sum].

Step-by-Step Explanation

Using arr = [3, 34, 4, 12, 5, 2], sum = 9:

Step 1: Initialize. Row 0 (no elements): dp[0][0] = true, dp[0][1..9] = false. Column 0: all true.

Step 2: Row 1, element = 3. j=1: dp[1][1] = dp[0][1] = false. j=2: false. j=3: dp[0][3] || dp[0][0] = false || true = true. We can make sum 3 using {3}.

Step 3: j=9 (target): dp[1][9] = dp[0][9] || dp[0][6] = false. Can't reach 9 with just {3}.

Step 4: Row 2, element = 34. Since 34 > 9, for all j ≤ 9: dp[2][j] = dp[1][j]. No new sums reachable.

Step 5: Row 3, element = 4. j=4: dp[2][4] || dp[2][0] = false || true = true. Sum 4 = {4}.

Step 6: j=7: dp[2][7] || dp[2][3] = false || true = true. Sum 7 = {3, 4}.

Step 7: j=9: dp[2][9] || dp[2][5] = false || false = false. Still can't make 9 with {3, 34, 4}.

Step 8: Row 4, element = 12. Since 12 > 9, no changes for j ≤ 9.

Step 9: Row 5, element = 5. j=5: dp[4][5] || dp[4][0] = false || true = true. Sum 5 = {5}.

Step 10: j=9: dp[4][9] || dp[4][4] = false || true = TRUE! Sum 9 = {4, 5}. Target achieved!

Step 11: dp[5][9] = true. A subset of the first 5 elements sums to 9. Answer: true.

2D DP Table — Building Reachable Sums Row by Row — Watch the boolean DP table fill row by row as each element is considered. Green (true) cells spread as more sums become reachable. The target cell dp[5][9] turns true when element 5 is processed.

Algorithm

  1. Create a 2D boolean array dp[n+1][sum+1] initialized to false
  2. Set dp[i][0] = true for all i (empty subset achieves sum 0)
  3. For each element i from 1 to n:
    • For each target j from 1 to sum:
      • If arr[i-1] > j: dp[i][j] = dp[i-1][j] (can't include this element)
      • Else: dp[i][j] = dp[i-1][j] OR dp[i-1][j - arr[i-1]]
  4. Return dp[n][sum]

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isSubsetSum(vector<int>& arr, int sum) {
        int n = arr.size();
        vector<vector<bool>> dp(n + 1,
            vector<bool>(sum + 1, false));

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j]
                        || dp[i - 1][j - arr[i - 1]];
            }
        }
        return dp[n][sum];
    }
};
class Solution:
    def isSubsetSum(self, arr: list[int], target: int) -> bool:
        n = len(arr)
        dp = [[False] * (target + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = True

        for i in range(1, n + 1):
            for j in range(1, target + 1):
                if arr[i - 1] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = (dp[i - 1][j]
                        or dp[i - 1][j - arr[i - 1]])

        return dp[n][target]
class Solution {
    public boolean isSubsetSum(int[] arr, int sum) {
        int n = arr.length;
        boolean[][] dp = new boolean[n + 1][sum + 1];

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (arr[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j]
                        || dp[i - 1][j - arr[i - 1]];
            }
        }
        return dp[n][sum];
    }
}

Complexity Analysis

Time Complexity: O(n × sum)

We fill a table of size (n+1) × (sum+1). Each cell takes O(1) to compute (just a lookup and an OR). For n = 200 and sum = 10,000: 200 × 10,000 = 2,000,000 operations.

Space Complexity: O(n × sum)

The 2D boolean array stores (n+1) × (sum+1) entries. For n = 200 and sum = 10,000, this is about 2 million booleans (~2 MB). Manageable, but we can do better.

Why This Approach Is Not Efficient

The tabulation approach uses O(n × sum) space for the 2D table. While 2 million booleans is fine for this problem's constraints, the space can become a concern for larger inputs or when memory is limited.

A key observation: when filling row i, we only read values from row i-1. We never look two rows back. This means we don't need to keep the entire table — just the previous row and the current row.

But we can go even further: if we iterate the target values right-to-left (from sum down to arr[i-1]), we can update the array in place using a single 1D array. The right-to-left iteration ensures that when we check dp[j - arr[i-1]], it still holds the value from the previous row (not yet overwritten in this pass). This reduces space from O(n × sum) to O(sum).

Optimal Approach - Space Optimized DP

Intuition

We maintain a single 1D boolean array dp[0..sum] where dp[j] = true means "sum j is achievable using elements processed so far."

For each element arr[i], we scan the array right-to-left (from j = sum down to j = arr[i]). For each j, we set dp[j] = dp[j] OR dp[j - arr[i]]. This means: "sum j is achievable either from a subset that doesn't use arr[i] (the existing dp[j]), or from a subset that uses arr[i] (which would need sum j - arr[i] to be already achievable)."

The right-to-left scan is critical: if we went left-to-right, updating dp[j - arr[i]] first could pollute the value we need later at dp[j], effectively allowing an element to be used multiple times.

After processing all elements, dp[sum] holds the answer.

Step-by-Step Explanation

Using arr = [3, 34, 4, 12, 5, 2], sum = 9:

Step 1: Initialize dp = [T, F, F, F, F, F, F, F, F, F]. Only sum 0 is achievable.

Step 2: Process element 3. Scan j from 9 down to 3.

  • j=9: dp[9] || dp[6] = F || F = F.
  • j=3: dp[3] || dp[0] = F || T = T. Sum 3 achievable via {3}.
  • Result: dp = [T, F, F, T, F, F, F, F, F, F]

Step 3: Process element 34. Since 34 > 9, no cell in range [0..9] can be updated. Skip.

Step 4: Process element 4. Scan j from 9 down to 4.

  • j=9: dp[9] || dp[5] = F || F = F.
  • j=7: dp[7] || dp[3] = F || T = T. Sum 7 = {3, 4}.
  • j=4: dp[4] || dp[0] = F || T = T. Sum 4 = {4}.
  • Result: dp = [T, F, F, T, T, F, F, T, F, F]

Step 5: Process element 12. Since 12 > 9, skip.

Step 6: Process element 5. Scan j from 9 down to 5.

  • j=9: dp[9] || dp[4] = F || T = TRUE! Target reached! Sum 9 = {4, 5}.
  • j=8: dp[8] || dp[3] = F || T = T. Sum 8 = {3, 5}.
  • j=5: dp[5] || dp[0] = F || T = T. Sum 5 = {5}.
  • Result: dp = [T, F, F, T, T, T, F, T, T, T]

Step 7: dp[9] = true. Answer: true. We can still process element 2, but the result is already determined.

1D Space-Optimized DP — Right-to-Left Scan — Watch a single 1D array update as each element is processed. Scanning right-to-left prevents double-counting. The target cell dp[9] turns true when element 5 is processed.

Algorithm

  1. Create a 1D boolean array dp[sum+1] initialized to false
  2. Set dp[0] = true (empty subset sums to 0)
  3. For each element arr[i]:
    • If arr[i] > sum, skip this element
    • Scan j from sum down to arr[i]:
      • dp[j] = dp[j] OR dp[j - arr[i]]
  4. Return dp[sum]

Why right-to-left? If we went left-to-right, updating dp[4] before dp[7] with element 4 would make dp[7] use the new dp[3] (which might include element 4 again), effectively allowing element 4 to be used multiple times. Right-to-left ensures we only read values from the "previous row."

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isSubsetSum(vector<int>& arr, int sum) {
        int n = arr.size();
        vector<bool> dp(sum + 1, false);
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= arr[i]; j--) {
                dp[j] = dp[j] || dp[j - arr[i]];
            }
        }
        return dp[sum];
    }
};
class Solution:
    def isSubsetSum(self, arr: list[int], target: int) -> bool:
        dp = [False] * (target + 1)
        dp[0] = True

        for num in arr:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]
class Solution {
    public boolean isSubsetSum(int[] arr, int sum) {
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

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

Complexity Analysis

Time Complexity: O(n × sum)

We iterate through n elements. For each element, we scan up to sum entries in the dp array. Total: O(n × sum). Same as the 2D tabulation approach.

Space Complexity: O(sum)

We maintain a single 1D array of size sum + 1. For sum = 10,000, this is 10,001 booleans (~10 KB) — a dramatic reduction from the 2D table's 2 MB. This is the most space-efficient DP solution possible for this problem.