Log inSign up
mediumGeeksforGeeksNot Started

Subset Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of non-negative integers arr and a target integer sum, determine if there is a subset of the given array with sum equal to sum.

Return true if such a subset exists, otherwise false.

### Example 1 - Input: arr = [3, 34, 4, 12, 5, 2], sum = 9 - Output: true - Explanation: There is a subset [4, 5] with sum 9.

### Example 2 - Input: arr = [3, 34, 4, 12, 5, 2], sum = 30 - Output: false - Explanation: There is no subset that adds up to 30.

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000
  • 1 <= sum <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the foundational 0/1 Knapsack state formulation.
  • Implement single-array space reduction with reverse looping.
  • Leverage early-exit conditions for average-case speedups.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determining if elements in an array can sum to an exact target.
  • Each element can be used at most once.

Algorithmic Decision Tree:

  • 0/1 knapsack pattern -> backward loop for 1D space optimization.

Connected Patterns:

Partition Equal Subset SumMinimum Subset Sum DifferenceTarget Sum

1. Recursive Inclusion / Exclusion

Intuition

Recursively branch whether each element is included or excluded from the subset.

Algorithm

  1. Define solve(idx, rem).
  2. If rem == 0, return true.
  3. If idx == n || rem < 0, return false.
  4. Return solve(idx + 1, rem - arr[idx]) || solve(idx + 1, rem).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 bool solve(int idx, int rem, const vector<int>& arr) {
8 if (rem == 0) return true;
9 if (idx == arr.size() || rem < 0) return false;
10 return solve(idx + 1, rem - arr[idx], arr) || solve(idx + 1, rem, arr);
11 }
12public:
13 bool isSubsetSum(vector<int>& arr, int sum) {
14 return solve(0, sum, arr);
15 }
16};
17
18int main() {
19 Solution sol;
20 vector<int> arr = {3, 34, 4, 12, 5, 2};
21 cout << (sol.isSubsetSum(arr, 9) ? "true" : "false") << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 2D Tabulation DP

Intuition

Build an explicit 2D boolean array dp[n + 1][sum + 1].

Algorithm

  1. Initialize dp[n + 1][sum + 1] with false; dp[i][0] = true.
  2. For i from 1 to n:
  3. For s from 1 to sum:
  4. dp[i][s] = dp[i-1][s] || (s >= arr[i-1] ? dp[i-1][s - arr[i-1]] : false).
  5. Return dp[n][sum].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 bool isSubsetSum(vector<int>& arr, int sum) {
9 int n = arr.size();
10 vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
11 for (int i = 0; i <= n; ++i) dp[i][0] = true;
12
13 for (int i = 1; i <= n; ++i) {
14 for (int s = 1; s <= sum; ++s) {
15 dp[i][s] = dp[i - 1][s];
16 if (s >= arr[i - 1]) {
17 dp[i][s] = dp[i][s] || dp[i - 1][s - arr[i - 1]];
18 }
19 }
20 }
21
22 return dp[n][sum];
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> arr = {3, 34, 4, 12, 5, 2};
29 cout << (sol.isSubsetSum(arr, 9) ? "true" : "false") << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n * sum)
  • Space complexity: O(n * sum)

3. Space-Optimized 1D Reverse Boolean Array

Intuition

Use a single 1D boolean array of size sum + 1 traversed in reverse from sum down to num.

Algorithm

  1. Initialize boolean array dp of size sum + 1 with false; dp[0] = true.
  2. For each num in arr:
  3. For s from sum down to num:
  4. dp[s] = dp[s] || dp[s - num].
  5. If dp[sum] is true, return true immediately.
  6. Return dp[sum].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 bool isSubsetSum(vector<int>& arr, int sum) {
9 vector<bool> dp(sum + 1, false);
10 dp[0] = true;
11
12 for (int num : arr) {
13 for (int s = sum; s >= num; --s) {
14 dp[s] = dp[s] || dp[s - num];
15 }
16 if (dp[sum]) return true;
17 }
18
19 return dp[sum];
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> arr = {3, 34, 4, 12, 5, 2};
26 cout << (sol.isSubsetSum(arr, 9) ? "true" : "false") << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n * sum)
  • Space complexity: O(sum)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(2^n)O(n)Exhaustive branching over inclusion/exclusion.Overlapping subsets
2.2D TabulationO(n * sum)O(n * sum)Fill 2D boolean reachability table.Matrix allocation
3.1D Reverse Boolean ArrayOptimalO(n * sum)O(sum)Single 1D boolean array traversed backwards.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating forward in 1D DP (turns 0/1 knapsack into unbounded knapsack).

Pitfall 2:

Not initializing dp[0] = true.

Crucial Edge Cases to Validate:

  • sum = 0: Empty subset always has sum 0; returns true.
  • Any single element == sum: Returns true immediately.
  • Sum of all elements < sum: Impossible; returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this is the canonical 0/1 Knapsack decision problem and is NP-complete.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the inner loop in the 1D DP approach iterate backwards (from sum down to num)?

Back to DSA Sheet