Check If a Subset with the Target Sum Exists

55.1k
0

Given an array arr containing n positive integers and a non-negative integer target, select each array position at most once. Return true if the sum of selected elements equals target; otherwise, return false. The empty subset has a sum of 0.

Example 1

Input: arr = [1, 2, 3, 4], target = 4
Output: true
Explanation: Subset [4] reaches the target. Subset [1, 3] also reaches the target.

Example 2

Input: arr = [2, 4, 6], target = 5
Output: false
Explanation: No subset of the array has a sum equal to 5.

Recursion

Every array value gives us two choices: exclude it from the subset or include it. We explore both choices, and because finding just one valid subset is enough, we combine their results using logical OR.

The state solve(index, remaining) represents whether a subset can be formed using elements from positions 0 through index with a required sum of remaining. The initial call starts at the last index with the complete target because the entire array and target are available. After making a choice, we move to index - 1, ensuring that each array element is considered at most once.

Algorithm

  • Start with solve(index, remaining) so the available array prefix and required sum are tracked at every step.

  • Return true when remaining == 0 because the selected elements already form the target sum.

  • At index == 0, compare arr[0] with remaining because only the first element is left to consider.

  • Explore solve(index - 1, remaining) for the choice of excluding the current element.

  • Explore the taken choice only when arr[index] <= remaining, because positive values cannot be used if they exceed the remaining sum.

  • For a valid taken choice, call solve(index - 1, remaining - arr[index]) because the current value is included exactly once.

  • Return the logical OR of the taken and not-taken results because either successful choice proves that the target sum can be formed.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks subset existence inside one prefix.
bool solve(vector<int>& arr, int index, int remaining) {
// A zero remainder confirms a valid subset.
if (remaining == 0) {
return true;
}
// The first value has one possible match.
if (index == 0) {
return arr[0] == remaining;
}
// Skipping keeps the required sum unchanged.
bool notTaken = solve(arr, index - 1, remaining);
// A taken branch starts unavailable.
bool taken = false;
// Taking stays valid inside the required sum.
if (arr[index] <= remaining) {
// Taking removes the selected value once.
taken = solve(
arr,
index - 1,
remaining - arr[index]
);
}
// Either valid choice proves subset existence.
return taken || notTaken;
}
public:
// Checks the full array for the target sum.
bool subsetSumToTarget(vector<int>& arr, int target) {
int n = arr.size();
// The final index exposes every array value.
return solve(arr, n - 1, target);
}
};
// Driver code
int main() {
vector<int> arr = {1, 2, 3, 4};
int target = 4;
Solution obj;
cout << boolalpha << obj.subsetSumToTarget(arr, target);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of elements in the array, because each element creates two choices—take or skip—resulting in an exponential number of recursive calls.

Space Complexity: O(N), where N is the number of elements in the array, because the deepest recursive path can contain at most one call for each element.

Memoization

Direct recursion can revisit the same (index, remaining) state through different take-or-skip paths. Repeating an identical state repeats an identical answer.

A 2D array named dp stores every solved state. Value -1 marks an untouched state, while 0 and 1 store false and true results. Cache reuse keeps the recursive idea unchanged and removes duplicate work.

Algorithm

  • Begin with the same solve(index, remaining) state so memoization preserves every recursive choice and base case.

  • Create dp with n rows and target + 1 columns, filled with -1, so every unfinished state has a clear marker.

  • Return true for remaining = 0, and compare the first value at index = 0, because both stopping conditions already have final answers.

  • Reuse dp[index][remaining] after a solved-state check so another path never rebuilds the same recursion tree.

  • Compute the not-taken state with an unchanged sum, then compute the taken state only inside the remaining-sum limit because positive values cannot repair an exceeded sum.

  • Store the logical OR in dp[index][remaining] because one successful branch is enough for the current state.

  • Return the cached result from the full state (n - 1, target) because the state covers every allowed position and the complete target.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks and stores one subset-sum state.
bool solve(
vector<int>& arr,
int index,
int remaining,
vector<vector<int>>& dp
) {
// A zero remainder confirms a valid subset.
if (remaining == 0) {
return true;
}
// The first value has one possible match.
if (index == 0) {
return arr[0] == remaining;
}
// A stored value avoids repeated recursion.
if (dp[index][remaining] != -1) {
return dp[index][remaining] == 1;
}
// Skipping keeps the required sum unchanged.
bool notTaken = solve(
arr,
index - 1,
remaining,
dp
);
// A taken branch starts unavailable.
bool taken = false;
// Taking stays valid inside the required sum.
if (arr[index] <= remaining) {
// Taking removes the selected value once.
taken = solve(
arr,
index - 1,
remaining - arr[index],
dp
);
}
// Cache the OR because either choice can work.
dp[index][remaining] = taken || notTaken;
// Return the stored answer for the state.
return dp[index][remaining] == 1;
}
public:
// Checks the full array with memoization.
bool subsetSumToTarget(vector<int>& arr, int target) {
int n = arr.size();
// Minus one marks every state as untouched.
vector<vector<int>> dp(
n,
vector<int>(target + 1, -1)
);
// The final index exposes every array value.
return solve(arr, n - 1, target, dp);
}
};
// Driver code
int main() {
vector<int> arr = {1, 2, 3, 4};
int target = 4;
Solution obj;
cout << boolalpha << obj.subsetSumToTarget(arr, target);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of elements and target is the target sum, because at most N × (target + 1) states are solved once, with constant work per state.

Space Complexity: O(N × target + N), where N is the number of elements and target is the target sum, because the dp table stores all states and the recursion stack can contain at most O(N) calls.

Tabulation

Memoization answers states on demand. Tabulation fills the same states in a fixed order, so recursive calls and call-stack storage disappear.

Row index uses only row index - 1. Every sum in the earlier row is ready before the next row begins, allowing the take and skip transitions to match the recursive choices directly.

Algorithm

  • Begin with a boolean table dp containing n rows and target + 1 columns so every (index, sum) state has a direct stored answer.

  • Mark dp[index][0] = true for every row because the empty subset forms sum 0 from every usable prefix.

  • Mark dp[0][arr[0]] = true inside the target limit because the first value alone forms exactly one reachable positive sum.

  • Process rows from index 1 to n - 1 so every transition reads a fully prepared previous row.

  • Read dp[index - 1][sum] for the not-taken choice because skipping preserves the unfinished sum.

  • Read dp[index - 1][sum - arr[index]] only inside the sum limit because the earlier row must represent a non-negative remainder, then combine both choices with logical OR.

  • Return dp[n - 1][target] because the final cell represents all values and the complete required target.

Dry Run

subset-sum-tabulation-state-indices

subset-sum-tabulation-state-indices

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks subset existence with a DP table.
bool subsetSumToTarget(vector<int>& arr, int target) {
int n = arr.size();
// Each cell records one reachable sum.
vector<vector<bool>> dp(
n,
vector<bool>(target + 1, false)
);
// Sum zero needs no selected values.
for (int index = 0; index < n; index++) {
dp[index][0] = true;
}
// The first value forms one positive sum.
if (arr[0] <= target) {
dp[0][arr[0]] = true;
}
// Later rows depend on a completed earlier row.
for (int index = 1; index < n; index++) {
// Every target sum receives two choices.
for (int sum = 1; sum <= target; sum++) {
// Skipping keeps the required sum unchanged.
bool notTaken = dp[index - 1][sum];
// A taken state starts unavailable.
bool taken = false;
// Taking stays valid inside the current sum.
if (arr[index] <= sum) {
// The earlier row supplies the remainder.
taken = dp[index - 1][sum - arr[index]];
}
// Either choice makes the sum reachable.
dp[index][sum] = taken || notTaken;
}
}
// The final cell covers the complete problem.
return dp[n - 1][target];
}
};
// Driver code
int main() {
vector<int> arr = {1, 2, 3, 4};
int target = 4;
Solution obj;
cout << boolalpha << obj.subsetSumToTarget(arr, target);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of elements and target is the target sum, because the table fills N × (target + 1) states, with constant work per state.

Space Complexity: O(N × target), where N is the number of elements and target is the target sum, because the table stores every prefix and target-sum state, with no recursion stack.

Space Optimization

Every tabulation row depends only on the previous row. Older rows are never used again, so the full two-dimensional table is unnecessary. We can replace it with two one-dimensional arrays.

The array previous stores the results for the already processed elements, while current stores the results for the newly processed element. After completing an entire row, current becomes previous. The shift happens only after all sums are calculated, ensuring that every transition uses values from the previous row.

Algorithm

  • Create a boolean array previous of size target + 1, so one row can represent whether each sum is reachable.

  • Set previous[0] = true because sum 0 is always possible using an empty subset.

  • Process each array value one by one, creating a fresh current array so take transitions always read from the unchanged previous row.

  • Set current[0] = true because sum 0 remains reachable for every prefix.

  • Calculate each current[sum] using previous[sum] for the skip choice and previous[sum - value] for the take choice, preserving the original tabulation transitions.

  • Replace previous with current only after the entire row is calculated, because the next value needs the completed current row.

  • Return previous[target] after processing all values, because it represents the reachable sums using the complete array.

Dry Run

subset-sum-space-optimization-state-indices-no-logo.png

subset-sum-space-optimization-state-indices-no-logo.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks subset existence with two DP rows.
bool subsetSumToTarget(vector<int>& arr, int target) {
int n = arr.size();
// The retained row stores earlier-prefix answers.
vector<bool> previous(target + 1, false);
// Sum zero needs no selected values.
previous[0] = true;
// The first value forms one positive sum.
if (arr[0] <= target) {
previous[arr[0]] = true;
}
// Each later value builds one fresh row.
for (int index = 1; index < n; index++) {
// Fresh storage protects earlier-row answers.
vector<bool> current(target + 1, false);
// Sum zero remains reachable in every row.
current[0] = true;
// Every target sum receives two choices.
for (int sum = 1; sum <= target; sum++) {
// Skipping reads the unchanged earlier state.
bool notTaken = previous[sum];
// A taken state starts unavailable.
bool taken = false;
// Taking stays valid inside the current sum.
if (arr[index] <= sum) {
// The earlier row supplies the remainder.
taken = previous[sum - arr[index]];
}
// Current combines take and skip answers.
current[sum] = taken || notTaken;
}
// Shift only after the full row is complete.
previous = current;
}
// The retained row covers the complete problem.
return previous[target];
}
};
// Driver code
int main() {
vector<int> arr = {1, 2, 3, 4};
int target = 4;
Solution obj;
cout << boolalpha << obj.subsetSumToTarget(arr, target);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of elements and target is the target sum, because each of the N elements calculates every sum from 0 through target once.

Space Complexity: O(target), where target is the target sum, because two boolean rows of length target + 1 replace the full dp table.

Interview follow-up Questions

Yes. The empty subset has sum 0, so every approach returns true immediately for target 0.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

Input: prices = [1, 3, 2, 8, 4, 9] , fee = 2 Output: 8 Explanation: Buying at 1 and selling at 8 earns 8 - 1 - 2 = 5 . Buying at 4 and selling at 9 earns 9 - 4 - 2 = 3 . The maximum total profit is...

65.7k
Comments0