Subset Sum — The Target-Sum Subset Problem, with a Detailed DP Solution

What Is Subset Sum?

Given a set of integers S = {s₁, s₂, ..., sₙ} and a target sum T. The question is: Does there exist a subset of elements from S whose sum is exactly T?

Each element can either be included in the subset or excluded, so the solution is selected from all possible combinations of elements.

Example: S = {3, 1, 5, 9, 12}, T = 9 → answer: yes (one possible subset is {3,1,5}).

Problem Description

Given set S and target sum T, determine:

whether a subset with sum exactly T exists,
optionally, find one or all subsets whose sum equals T.

Each element may be included at most once. The subset may be empty if T = 0.

Possible Problem Variants

Decision problem: Returns a yes/no answer indicating whether a subset with sum T exists.
Counting problem: Count how many distinct subsets have sum T.
Construction problem: Find and return one or all subsets with sum T.
Optimization: Find a subset whose sum is as close as possible to T if T cannot be reached exactly.

Worked Example with Concrete Numbers

Input:

Set: S = {3, 1, 5, 9, 12}
Target sum: T = 9

Explanation:

Possible subsets with sum 9: {3,1,5}, {9}
Each element is either selected or not selected; elements cannot be split or used more than once.

Output:

Does a subset with sum T exist? → yes
Example of one subset: {3,1,5}

Notes and Recommendations

This is a classic NP-complete problem in the general case, but it is often solved with dynamic programming when the numbers are non-negative and T is not too large.
Efficient approaches include:
- top-down recursion with memoization (each subproblem is checked only once),
- bottom-up tabulation (filling the DP table from 0 to T),
- bitset optimization for small or moderate values of T,
- the meet-in-the-middle approach for a larger number of elements (n ≤ 40).
With negative numbers, the problem becomes more complex and requires additional techniques (sum offsets or hash maps).

This problem is an excellent exercise for understanding dynamic programming and overlapping subproblems.

Brute Force (Why It Is Not Enough)

The simplest approach tries all subsets — there are 2ⁿ. This is feasible only for small n (n ≤ 20). A more efficient solution is needed.

Dynamic Programming — The Basic Idea

We define a boolean DP array:

dp[sum] = true if the sum 'sum' can be formed using the elements processed so far

Initially: dp[0] = true (the empty subset gives sum 0); all other dp[x] are initially false. When processing a new number num, we update dp to include all new sums obtained by adding num to sums that were already achievable.

for (int num : S) {
    for (int sum = T; sum >= num; --sum) {
      dp[sum] = dp[sum] || dp[sum - num];
    }
  }

Why Do We Iterate Backwards (from T to num)?

If we iterated forwards (from num to T), the new value dp[x] could affect larger sums in the same iteration and allow the same element to be used multiple times — changing the problem into unbounded knapsack.
Iterating backwards guarantees that the new sum dp[sum] is obtained only from the old (previous) states dp[sum - num], so the same element is not used more than once.

Intuitive Explanations and Analogies (Blocks / Weights)

Analogy: Imagine the elements as the weights of blocks or weights on a scale. We have several weights, each with its own weight value. dp[x] = true means “you can make a total weight of x in your backpack.”

- If you have only a weight of 3, you can make totals of 0 (an empty backpack) and 3 (by taking that weight). All other totals are impossible. - When you later get another weight, say 4, you can now make 4 (using that weight alone) and 7 (3+4). - It is important to remember all achievable totals so far (`dp` values), because future weights may let you combine with exactly those values.

Detailed Step-by-Step Examples

Example A — One Element Only: {3}, Target T = 6

Initially: dp[0] = true, the rest are false.

After processing 3:

sum	0	1	2	3	4	5	6
dp	true	false	false	true	false	false	false

Explanation: we can either take weight 3 or leave it, giving totals 0 or 3. Totals 1 and 2 are impossible because we do not have a block with a smaller value.

Example B — Adding a Second Element: {3, 4}, Target T = 7

State before the second element (after 3): dp[0]=T, dp[3]=T.

We process num = 4. New achievable totals are obtained by adding 4 to every previously true state:

0 + 4 = 4 → dp[4] = true
3 + 4 = 7 → dp[7] = true

sum	0	1	2	3	4	5	6	7
dp	true	false	false	true	true	false	false	true

Conclusion: dp[5] remains false because, for 5 to be possible, dp[1] would have to be true beforehand (then 1+4=5). Since dp[1] = false, 5 cannot be formed.

Example C — Adding a Third Element: {3, 4, 2}, Target T = 6

After the previous steps, dp[4]=true and dp[3]=true. Now process num = 2 (iterate over sums backwards):

dp[6] |= dp[4] → dp[6] = true (because dp[4] = true and 4+2 = 6)
dp[5] |= dp[3] → dp[5] = true (because dp[3] = true and 3+2 = 5)
dp[2] |= dp[0] → dp[2] = true

Final state (up to 6): dp[6]=true → target reached.

Why Do We Store All dp[1..T] States?

We store all intermediate results because we do not know which elements will appear later. Each subsequent number can be combined with any sum already achieved. If we do not store dp[3] now, we will not be able to form 3+2=5 later. Thus, even sums that do not seem useful right now may be essential in later steps.

Why Do We Iterate Backwards? (A More Detailed Explanation)

We use a one-dimensional dp array to optimize memory. If we iterate over sums forwards (from num to T), newly computed values from the same iteration may be reused, which means the same element could be used multiple times (which is not desired). Iterating backwards dp[sum] depends only on the old values dp[sum-num], ensuring that each element is included at most once.

Implementation (C++)

An efficient implementation using O(T) memory:


// Subset Sum (boolean) -- O(n * T) time, O(T) memory
#include <iostream>
#include <vector>
using namespace std;

bool subsetSum(const vector<int>& S, int T) {
    vector<bool> dp(T+1, false);
    dp[0] = true;
    for (int num : S) {
        for (int sum = T; sum >= num; --sum) {
            dp[sum] = dp[sum] || dp[sum - num];
        }
    }
    return dp[T];
}

int main() {
    vector<int> S = {3, 4, 2};
    int T = 6;
    cout << (subsetSum(S, T) ? "Yes\\n" : "No\\n");
    return 0;
}

Code Explanation

dp[sum] indicates whether the sum is possible using the elements processed so far.
The loop for (int sum = T; sum >= num; --sum) ensures that the new element is not used more than once.
At the end of the function, we return dp[T] — whether the target sum is possible.

Complexity

Time complexity: O(n · T)
Space: O(T) (this can be optimized further in special cases)

Tips and Common Mistakes

Do Not Iterate Forwards (from num to T) — this leads to the error of using an element more than once.
Remember that dp[0] must always be true (the empty subset).
If the numbers or T are very large, DP may become slow or memory-intensive. Consider alternative approaches or optimizations (e.g. bitset optimization, meet-in-the-middle for n ≤ 40, or heuristics).
For counting the number of ways (how many subsets have sum T), the logic is similar, but you must store counts (long long) and watch for overflow or use modulo arithmetic if needed.

Quick Summary (for Students)

Define dp[sum] — whether the sum is possible.
Start with dp[0] = true, and set the rest to false.
For each number num update dp backwards: for sum = T..num perform dp[sum] |= dp[sum-num].
Finally, check dp[T].

Visual DP Table (Step by Step)

Example: S = {3, 4, 2}, target sum T = 6. Each row represents the state of dp[] after processing one number.

Step	0	1	2	3	4	5	6
Initial state	T	F	F	F	F	F	F
After 3	T	F	F	T	F	F	F
After 4	T	F	F	T	T	F	T
After 2	T	F	T	T	T	T	T

The visual table clearly shows how each new value of num enables new exact sums, and how dp[] gradually fills up until we reach the target T = 6.

Intuitive Visual Illustration — Blocks / Weights

Problem Subset Sum can be viewed as placing weights on the left side of a scale. We have a set of available weights (the numbers) and want to see which totals can be made by combining them.

Example: S = {3, 4, 2}, target sum T = 6.

Step 1: Initial State

--→0123456

Initially, we can make only the sum of 0 because we have not placed any weights.

Step 2: Add Weight 3

3→0123456

The only new sum we can form is 3, because 0 is achievable and 0 + 3 = 3.

Step 3: Add Weight 4

34→0123456

We now get the following new possible sums:

4 (because 0 + 4 = 4)
7 (0 + 3 + 4 = 7, but > T=6, so we ignore it for the target sum)

Step 4: Add Weight 2

342→0123456

Weight 2 adds several more possible sums:

2 (0 + 2)
5 (3 + 2)
6 (4 + 2)

We can now form all sums up to 6, including the target sum T=6.

Conclusion

The visual model with weights helps explain the key idea: all sums that may be needed later must be stored in dp[] while we build the solution. This shows how adding each element “builds” new possible sums from the previous ones.

Subset Reconstruction — Which Numbers Make Up Each Sum?

When we solve Subset Sum using only the boolean DP array dp[sum], we know whether a sum is possible, but do not know which numbers. Therefore, we create a separate structure that stores:

parent[sum] = (previous_sum, added_number)

This lets us “work backwards” from the target sum T, tracking which number formed it and which sum existed before it.

Example

Set: {3, 4, 5}
Target sum: T = 7

How to Fill the parent Table:

Sum	dp[sum]	parent[sum]	Explanation
3	true	(0, 3)	3 can be formed directly using the number 3
4	true	(0, 4)	4 can be formed directly using the number 4
5	true	(0, 5)	5 can be formed directly using the number 5
7	true	(3, 4)	7 = 3 + 4 → the previously formed sum 3 is used

□ Reconstructing the Subset for T = 7

Start: 7  
parent[7] = (3, 4)  → means we took 4  
parent[3] = (0, 3)  → means we took 3  
parent[0] = end

Solution:

{ 3, 4 }

C++ Code for Tracking the Subset

vector<bool> dp(T+1, false);
vector<pair<int,int>> parent(T+1, {-1,-1});

dp[0] = true;

for (int num : a) {
    for (int sum = T; sum >= num; --sum) {
        if (dp[sum - num] && !dp[sum]) {
            dp[sum] = true;
            parent[sum] = {sum - num, num};
        }
    }
}

// Reconstruction
vector<int> subset;
int cur = T;

while (cur != 0 && parent[cur].first != -1) {
    subset.push_back(parent[cur].second);
    cur = parent[cur].first;
}

Visual Illustration of Reconstruction

7 ⬑ we added 4

3 ⬑ we added 3

0 (start)

This means the DP algorithm found that 7 can be formed through the chain:

7 = 3 + 4

Problem Statement — Subset Sum

Given an array of n positive integersnums[] and a target sum T.

Determine whether there exists a subset of array elements (each element can be used at most once) whose elements sum exactly to T.

If such a subset exists, print YES, otherwise print NO.

Input

The first line contains two integers n and T
The second line contains n positive integers — the array elements

Output

Print YES if a subset with sum T
Otherwise, print NO

Note

Each array element can be used at most once
The task only asks whether a solution exists; it does not require printing the subset itself

Solution — Subset Sum (DP with Memoization)

This section contains a complete guide and a fully explained solution for the problem “Subset Sum”. The goal is to deepen understanding of recurrence relations, memoization, and tabulation, which are core dynamic programming techniques.

Guide — Solution Idea

We have an array of positive numbers nums[] and the target sum T. We need to determine whether a subset of its elements sums exactly to T.

dp[i][sum] = whether sum 'sum' can be obtained using the first i elements

Recurrence relation:

dp[i][sum] = dp[i-1][sum] || dp[i-1][sum - nums[i-1]]

Intuition: for element nums[i-1] we can:

Exclude it → dp[i-1][sum]
Include it → dp[i-1][sum - nums[i-1]]

Base Cases

dp[0][0] = true (the empty set gives sum 0)
dp[0][sum ≠ 0] = false (we cannot obtain a positive sum using 0 elements)

Why DP?

Without memoization, ordinary recursion checks the same combinations repeatedly. DP stores results for sum-and-index states, avoiding exponential time complexity.

Top-down (Memoization)

We implement a function that checks the state defined by i and sum, and stores the results.

Bottom-up (Tabulation)

We create a DP array dp[0..T] or dp[0..n][0..T] and fill it in order.

Solution — C++ (top-down memoization)


// Subset Sum — top-down memoization
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> memo;

bool subsetSum(const vector<int>& nums, int i, int sum) {
    if (sum == 0) return true;
    if (i == 0) return false;
    if (memo[i][sum] != -1) return memo[i][sum];

    if (sum < nums[i-1]) 
        memo[i][sum] = subsetSum(nums, i-1, sum);
    else
        memo[i][sum] = subsetSum(nums, i-1, sum) || subsetSum(nums, i-1, sum - nums[i-1]);

    return memo[i][sum];
}

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> nums(n);
    for(int i=0;i<n;i++) cin >> nums[i];

    memo.assign(n+1, vector<int>(T+1, -1));

    cout << (subsetSum(nums, n, T) ? "YES" : "NO") << "\n";
    return 0;
}

Bottom-up Tabulation (Iterative)


// Subset Sum — bottom-up
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> nums(n);
    for(int i=0;i<n;i++) cin >> nums[i];

    vector<bool> dp(T+1,false);
    dp[0] = true; // empty subset

    for(int num : nums) {
        for(int sum = T; sum >= num; --sum) {
            dp[sum] = dp[sum] || dp[sum - num];
        }
    }

    cout << (dp[T] ? "YES" : "NO") << "\n";
}

Code Explanation

Top-down stores results for each index and sum to avoid repeated computation.
Bottom-up starts with the empty set and gradually combines numbers to form sums.
We iterate backwards (sum=T..num) so that values updated during the current iteration are not reused.

Example

Input:
5 9
3 34 4 12 5

Output:
YES

Explanation:
The subset {4, 3, 2} has a sum of 9.

Time and Space Complexity

Time: O(n*T)
Space: O(n*T) for two-dimensional DP or O(T) for optimized bottom-up DP

NP-Completeness and Limitations of the DP Solution

The Subset Sum problem is known to be NP-complete in the general case. Wikipedia explains the details. This means that, although the DP solution runs in O(n·T) (where n is the number of elements and T is the target sum), this is pseudopolynomial.

Pseudopolynomial means that the running time depends on the numeric values, not only on how many numbers there are. DP is very efficient for small numbers and moderate target sums. However, if the numbers and T are large, the running time may become impractical, and DP does not guarantee polynomial time in the general case.

Alternatives and Optimizations for Larger Values

When dealing with large numbers or a large T, more advanced techniques are available:

Meet-in-the-middle algorithm — splits the set into two halves and combines their sums; its complexity is O(2^{n/2}), often practical for n ≈ 40.
Heuristics and approximations — for problems where an exact solution is not required, these can provide faster answers.
Pseudopolynomial optimization — some DP variants can reduce memory use or running time, but still depend on the numeric values.

For more details and formal results, see arXiv: Pseudopolynomial Subset Sum Algorithms.

Conclusion: The DP solution to Subset Sum is very useful, but students and competitors should be aware of its limitations — it is not universally fast for every input.

Visualizing the Pseudopolynomial Growth of Subset Sum DP

The following table shows an example of how the DP array dp[0..T] grows as we increase the target sum and add numbers. Colors indicate whether a sum is possible (green) or not (red). This illustrates why DP becomes impractical when the numbers are large.

Numbers	T = 0	T = 1	T = 2	T = 3	T = 4	T = 5	T = 6
Initially	✔	✖	✖	✖	✖	✖	✖
+ Number 1	✔	✔	✖	✖	✖	✖	✖
+ Number 3	✔	✔	✖	✔	✖	✖	✔
+ Number 4	✔	✔	✖	✔	✔	✔	✔

Legend: ✔ the sum is achievable with the current subset; ✖ the sum is not achievable. This table shows how adding numbers makes more target sums achievable, while also illustrating how memory use grows with T. When T and the elements are large (e.g. T > 10⁵), the DP array becomes huge — even though the solution is correct, it is not practical.

Subset Sum — Visual Illustration of Subsets (Blocks / Weights)

The following illustration shows how different subsets of numbers can form particular target sums T. Each “block” represents a number in the set, and the rows show combinations that contribute to the sums.

Example set:nums = [1, 3, 4], target T = 6

Subset	Sum = 0	Sum = 1	Sum = 2	Sum = 3	Sum = 4	Sum = 5	Sum = 6
{ }	✔	✖	✖	✖	✖	✖	✖
{1}	✔	✔	✖	✖	✖	✖	✖
{3}	✔	✖	✖	✔	✖	✖	✖
{4}	✔	✖	✖	✖	✔	✖	✖
{1,3}	✔	✔	✖	✔	✖	✔	✖
{1,4}	✔	✔	✖	✖	✔	✔	✖
{3,4}	✔	✖	✖	✔	✔	✖	✔
{1,3,4}	✔	✔	✖	✔	✔	✔	✔

Legend: ✔ the sum is achievable with the given subset; ✖ it is not. Each row shows how combinations of elements contribute to forming the target sum T.

This illustration helps build an intuitive understanding of why DP fills the dp[sum] field from zero to T and combines previously stored results.

Subset Sum — Subset Reconstruction

In practical problems, it is often not enough to determine only whether the target sum T is possible. We may also need to find a subset that forms that sum. This can be done by storing, alongside the DP table, information about whether an element really had to be selected.

Solution Idea

We create a DP table dp[i][sum] which indicates whether sum sum is achievable using the first i elements.
The auxiliary table take[i][sum] is set to trueonly if taking the element is the only way to obtain that sum.
After filling the DP table, we start from dp[n][T] and move backwards, using take to reconstruct one valid subset.

C++ Code — Subset Reconstruction


// Subset Sum with reconstruction of one subset
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];

    vector<vector<bool>> dp(n+1, vector<bool>(T+1, false));
    vector<vector<bool>> take(n+1, vector<bool>(T+1, false));

    dp[0][0] = true;

    for(int i = 1; i <= n; i++) {
        for(int sum = 0; sum <= T; sum++) {

            // case: do not take nums[i-1]
            if(dp[i-1][sum]) {
                dp[i][sum] = true;
            }

            // case: take nums[i-1] (but only if this is the only way)
            if(sum >= nums[i-1] && dp[i-1][sum - nums[i-1]] && !dp[i-1][sum]) {
                dp[i][sum] = true;
                take[i][sum] = true;
            }
        }
    }

    if(!dp[n][T]) {
        cout << "No solution\n";
        return 0;
    }

    // subset reconstruction
    vector<int> subset;
    int sum = T;
    for(int i = n; i > 0; i--) {
        if(take[i][sum]) {
            subset.push_back(nums[i-1]);
            sum -= nums[i-1];
        }
    }

    cout << "Subset with sum " << T << ": ";
    for(int x : subset) cout << x << " ";
    cout << "\n";

    return 0;
}

Test Examples and Edge Cases

Example where a solution exists:nums = [1, 3, 4], T = 5 → subset: {1,4}.
Example where no solution exists:nums = [2,5,7], T = 4 → prints No solution.
Example where T is larger than the sum of all elements:nums = [1,2,3], T = 10 → no solution exists.
Example with duplicates:nums = [1,2,2,3], T = 4 → the subset can be {2,2} or {1,3}.

This implementation guarantees that the reconstructed subset is always consistent with the DP table. The take matrix is used only for decisions that were necessary, avoiding inconsistent reconstructions.

How Subset Reconstruction Works (Visual Explanation)

After the DP table dp has been filled, we know whether the target sum T is achievable, but we still do not know which elements were used. Therefore, we use the auxiliary table take.

The key idea is this:

take[i][sum] = true means that sum sumcannot be obtained without taking the element nums[i-1].

If the sum could also be obtained without that element, take[i][sum] remains false, even if taking it was also possible.

Example

Suppose the following numbers are given:


nums = [1, 3, 4]
T = 5

DP Table (1 = Possible)


        sum →
i ↓     0 1 2 3 4 5
-------------------
0       1 0 0 0 0 0
1 (1)   1 1 0 0 0 0
2 (3)   1 1 0 1 1 0
3 (4)   1 1 0 1 1 1

Marked `take` decisions

Let us see how dp[3][5]:

Without the number 4: dp[2][5] = false
With the number 4: dp[2][1] = true

Since no solution exists without the number 4, we set:


take[3][5] = true

Backward Traversal (Reconstruction)


Start: (i=3, sum=5)
  |
  |-- take[3][5] = true → take 4
  |
(i=2, sum=1)
  |
  |-- take[2][1] = false → do not take 3
  |
(i=1, sum=1)
  |
  |-- take[1][1] = true → take 1
  |
(i=0, sum=0)  ✓

The reconstructed subset is:


{1, 4}

Why Does This Always Work?

take is set only when the decision was unavoidable.
During reconstruction, we never enter a state that is not supported by the DP table.
We always obtain a valid subset without contradictions.

This approach provides a clear and reliable way to obtain, in addition to knowing whether a solution exists, a concrete example of the solution.

Variants of the Subset Sum Problem

1. Subset Sum — The Basic Problem (YES / NO)

Problem Statement

Given an array nums[ ] of n positive integers and a target sum T. Determine whether there is a subset of array elements whose sum is exactly T. Each element can be used at most once. If one exists, print YES, otherwise NO.

Example

Input:
5 9
3 34 4 12 5

Output:
YES

Explanation:
The subset {4, 3, 2} has a sum of 9.

Solution — bottom-up (optimized)


// Subset Sum -- bottom-up (O(T) space)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    if (!(cin >> n >> T)) return 0;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    vector<bool> dp(T + 1, false);
    dp[0] = true;

    for (int num : nums) {
        for (int s = T; s >= num; --s) {
            dp[s] = dp[s] || dp[s - num];
        }
    }

    cout << (dp[T] ? "YES" : "NO") << endl;
    return 0;
}

Note

For very large values of T (e.g. when the sum of the elements is very large), consider alternative approaches (meet-in-the-middle, input constraints).

2. Subset Sum — Reconstructing a Solution

Problem Statement

In addition to the YES/NO answer, return the actual subset of element indices that produces the sum T. If multiple solutions exist, return any one of them. If none exists, print NO.

Example

Input:
5 9
3 34 4 12 5

Output:
YES
Selected indices (1-based): 3 5

Explanation:
nums[3]=4, nums[5]=5 → 4+5=9

Solution — reconstruction from the 2D DP table


// Subset Sum -- reconstructing a solution from a 2D DP table
// Short and correct version WITHOUT an additional take matrix
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;

    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    // dp[i][s] = true if sum s can be obtained using the first i elements
    vector<vector<bool>> dp(n + 1, vector<bool>(T + 1, false));

    // Base case:
    // With 0 elements, only sum 0 can be obtained
    dp[0][0] = true;

    // Fill the DP table
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= T; s++) {

            // 1) Do not take the i-th element
            // If sum s was possible without it, it remains possible
            if (dp[i - 1][s]) {
                dp[i][s] = true;
            }

            // 2) Take the i-th element (if it does not exceed the current sum)
            // Check whether s - nums[i-1] was possible earlier
            if (s >= nums[i - 1] && dp[i - 1][s - nums[i - 1]]) {
                dp[i][s] = true;
            }
        }
    }

    // If the target sum is not reachable
    if (!dp[n][T]) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";

    // ============================
    // Solution reconstruction
    // ============================
    // Start from dp[n][T] and move backwards
    int s = T;
    vector<int> chosen;

    for (int i = n; i > 0; i--) {

        // If sum s was NOT possible without the i-th element,
        // then we HAD to take the i-th element
        if (s >= nums[i - 1] && !dp[i - 1][s]) {
            chosen.push_back(i);   // store the index (1-based)
            s -= nums[i - 1];      // decrease the remaining sum
        }

        // Otherwise, element i was not selected
        // simply move to i-1
    }

    // We collected indices backwards, so reverse them
    reverse(chosen.begin(), chosen.end());

    cout << "Selected indices: ";
    for (int idx : chosen)
        cout << idx << " ";
    cout << "\n";

    return 0;
}

Note

This version uses only the DP table dp and reconstructs the solution directly from it. The key idea is that an element is selected if the sum would not be possible without it. This gives a simpler and more robust solution without additional helper matrices.

3. Subset Sum — How Many Different Subsets Sum to T?

Problem Statement

Calculate the number of distinct subsets of the array nums whose sum is exactly T. Print the count (if overflow is possible, use a 64-bit type or modulo arithmetic).

Example

Input:
4 5
1 2 3 2

Output:
3

Explanation:
Subsets with sum 5: {1,2,2} (using different indices),
{2,3} (different choices of the index for 2) — 3 ways in total.

Guide

This is a counting variant of the Subset Sum problem (counting solutions rather than only checking existence).
DP definition:
dp[s] = the number of distinct subsets whose sum is exactly s.
Base case:
dp[0] = 1 (the empty set is one valid way).
Transition (1D optimization):
for each number num and each sum s (iterate backwards): dp[s] += dp[s - num].
Iterating over sums backwards is required so that each element is used at most once.

Mathematical Explanation of the DP Recurrence

Let dp[s] be the number of subsets that produce sum s using the first k array elements. Consider the next element num.

Every subset that produces sum s belongs to one of two disjoint groups:

Subsets that do not use the element num
— their count is already included in the current value of dp[s].
Subsets that use the element num
— if we remove num, the remaining elements must sum to s - num, and there are exactly this many such subsets: dp[s - num].

Since these two groups are disjoint, the total number of subsets with sum s is the sum of:

dp[s] = dp[s] + dp[s - num]

Iterating over sums backwards ensures each element is used at most once, because the values of dp[s - num] refer to the state before the current element was added.

In this way, DP counts all distinct subsets correctly; elements at different indices are considered distinct even when they have the same value.

Solution — Count the Ways (1D DP)


// Subset Sum — count the distinct subsets with sum T
// Time complexity: O(n * T)
// Space complexity: O(T)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    cin >> n >> T;

    // Read the array
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // dp[s] = number of subsets whose sum is exactly s
    vector<long long> dp(T + 1, 0);

    // One way to obtain sum 0 — the empty set
    dp[0] = 1;

    // For each array element
    for (int num : nums) {
        // Iterate over sums BACKWARDS so that the element is not used more than once
        for (int s = T; s >= num; --s) {
            dp[s] += dp[s - num];
            // If modulo is needed:
            // dp[s] %= 1000000007LL;
        }
    }

    // The answer is the number of subsets with sum T
    cout << dp[T] << "\n";
    return 0;
}

Note

If modulo arithmetic is not used and the number of combinations may be very large, use long long or unsigned long long, depending on the problem constraints.

4. Subset Sum — Minimum Number of Elements

Problem Statement

Find the minimum number of elements in the array nums such that their sum is exactly T. If this is impossible, print -1 (or print a message indicating that no solution exists).

Example

Input:
5 9
3 34 4 12 5

Output:
2

Explanation:
4 + 5 = 9 → minimum number of elements = 2

Solution — Minimum Number of Elements (1D DP)


// Subset Sum: minimum number of elements needed to reach sum T
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    if(!(cin >> n >> T)) return 0;

    // Read the array elements
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    // A large value representing "impossible"
    const int INF = 1000000000;

    // dp[s] = minimum number of elements required to obtain sum s
    vector<int> dp(T + 1, INF);

    // Base case: sum 0 is obtained using 0 elements
    dp[0] = 0;

    // Main DP loop
    for(int num : nums){
        // Iterate backwards to prevent using the same element more than once
        for(int s = T; s >= num; --s){
            // If sum (s - num) was possible,
            // check whether adding this element gives a better (smaller) solution
            if(dp[s - num] != INF){
                dp[s] = min(dp[s], dp[s - num] + 1);
            }
        }
    }

    // If dp[T] was not updated, no solution exists
    if(dp[T] == INF){
        cout << -1 << "\n";
    } else {
        cout << dp[T] << "\n";
    }

    return 0;
}

Note

This problem is a variant of the 0/1 Subset Sum problem, but instead of checking whether a solution exists, we seek the minimum. The DP structure stays the same; only the meaning of dp[s] and the transition change.

5. Connection to the 0/1 Knapsack Problem

Problem Statement / Idea

0/1 Knapsack: we have n items with weights w[i] and values v[i], and a knapsack capacity of W. The goal is to maximize the total value without exceeding the total weight of W.

Connection: Subset Sum is a special case of the Knapsack problem. If we set v[i] = w[i] and ask whether we can obtain exactly the value T, we get Subset Sum. Conversely, Knapsack is a generalization because it allows weights and values to differ.

Solution — 0/1 Knapsack (Bottom-up with Reconstruction)


// 0/1 Knapsack -- DP and reconstruction (2D DP table)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;

    // wt[i]  - weight of the i-th item
    // val[i] - value of the i-th item
    vector<int> wt(n), val(n);
    for (int i = 0; i < n; i++) cin >> wt[i];
    for (int i = 0; i < n; i++) cin >> val[i];

    // dp[i][w] = maximum value we can obtain
    // using the first i items and capacity w
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Fill the DP table
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {

            // 1) Do not take the i-th item
            dp[i][w] = dp[i - 1][w];

            // 2) Take the i-th item (if there is room in the knapsack)
            if (w >= wt[i - 1]) {
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]
                );
            }
        }
    }

    // Maximum achievable value
    cout << "Maximum value: " << dp[n][W] << "\n";

    // ============================
    // Reconstruct the selected items
    // ============================
    int w = W;
    vector<int> chosen;

    // Traverse the DP table backwards
    for (int i = n; i > 0; i--) {

        // If the value changed compared with the previous row,
        // the i-th item was selected
        if (dp[i][w] != dp[i - 1][w]) {
            chosen.push_back(i);     // store the index (1-based)
            w -= wt[i - 1];          // decrease the remaining capacity
        }
        // Otherwise, the item was not selected
    }

    // Reverse the order because we traversed backwards
    reverse(chosen.begin(), chosen.end());

    cout << "Selected items: ";
    for (int x : chosen) cout << x << " ";
    cout << "\n";

    return 0;
}

Practical Applications

Subset Sum can be viewed as Knapsack where weights and values are equal.
The reconstruction technique is the same in both problems — only the optimization criterion differs.
Understanding this connection makes it easier to recognize DP problems in practice.

6. Advanced Variants of Subset Sum

Problem Overview

Subset Sum with Negative Numbers
Unlimited use of elements (unbounded)
Meet-in-the-middle (n ≤ 40)
Closest sum ≤ T (approximation / closest)

Solution — Code Examples

a) Subset Sum with Negative Numbers — unordered_set


// Subset Sum with negative numbers using a set of sums
// Idea: store all achievable sums so far, without restricting them to [0..T]
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main(){
    int n, T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // Set of all currently reachable sums
    unordered_set<int> sums;
    sums.insert(0);  // the empty set gives sum 0

    for(int x : a){
        vector<int> add;
        // For each existing sum, add the new sum s + x
        for(int s : sums)
            add.push_back(s + x);

        // Add the new sums to the set
        for(int v : add)
            sums.insert(v);
    }

    cout << (sums.count(T) ? "YES\n" : "NO\n");
    return 0;
}

Note: This approach is practical when the number of distinct sums remains manageable. If the set grows too large, meet-in-the-middle is recommended.

b) Meet-in-the-middle (n ≤ 40)


// Meet-in-the-middle: check whether a subset with sum T exists
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Generate all possible subset sums of array a
void genSums(const vector<int>& a, vector<long long>& out){
    int m = a.size();
    int total = 1 << m; // 2^m combinations

    out.reserve(total);
    for(int mask = 0; mask < total; mask++){
        long long s = 0;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
                s += a[i];
        out.push_back(s);
    }
}

int main(){
    int n;
    long long T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int mid = n / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());

    vector<long long> L, R;
    genSums(left, L);
    genSums(right, R);

    sort(R.begin(), R.end());

    bool ok = false;
    for(long long x : L){
        long long need = T - x;
        if(binary_search(R.begin(), R.end(), need)){
            ok = true;
            break;
        }
    }

    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

c) Unlimited Use of Elements (Unbounded)


// Unbounded Subset Sum (Coin Change style)
// Each element can be used multiple times
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // dp[s] = whether sum s can be obtained
    vector<char> dp(T + 1, 0);
    dp[0] = 1;

    // Key difference: iterate over sums FORWARDS
    for(int i = 0; i < n; i++){
        for(int s = a[i]; s <= T; s++){
            if(dp[s - a[i]])
                dp[s] = 1;
        }
    }

    cout << (dp[T] ? "YES\n" : "NO\n");
    return 0;
}

d) Closest Sum ≤ T (Meet-in-the-middle)


// Meet-in-the-middle to find the largest sum <= T
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

void genSums(const vector<int>& a, vector<long long>& out){
    int m = a.size();
    int total = 1 << m;

    out.reserve(total);
    for(int mask = 0; mask < total; mask++){
        long long s = 0;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
                s += a[i];
        out.push_back(s);
    }
}

int main(){
    int n;
    long long T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int mid = n / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());

    vector<long long> L, R;
    genSums(left, L);
    genSums(right, R);

    sort(R.begin(), R.end());

    long long best = LLONG_MIN;

    for(long long x : L){
        long long rem = T - x;
        auto it = upper_bound(R.begin(), R.end(), rem);
        if(it != R.begin()){
            --it;
            best = max(best, x + *it);
        }
    }

    if(best == LLONG_MIN) cout << "NO\n";
    else cout << best << "\n";

    return 0;
}

Conclusion

These variants show how the basic Subset Sum problem can be extended by changing DP states, allowing repetition, or combining it with other techniques such as meet-in-the-middle.

Hidden Mini Quiz — The Subset Sum Problem

Click to test your understanding of the Subset Sum algorithm and the DP approach.

Open Quiz

Subset Sum — The Target-Sum Subset Problem, with a Detailed DP Solution

What Is Subset Sum?

Problem Description

Possible Problem Variants

Worked Example with Concrete Numbers

Notes and Recommendations

Brute Force (Why It Is Not Enough)

Dynamic Programming — The Basic Idea

Why Do We Iterate Backwards (from T to num)?

Intuitive Explanations and Analogies (Blocks / Weights)

Detailed Step-by-Step Examples

Example A — One Element Only: {3}, Target T = 6

Example B — Adding a Second Element: {3, 4}, Target T = 7

Example C — Adding a Third Element: {3, 4, 2}, Target T = 6

Why Do We Store All dp[1..T] States?

Why Do We Iterate Backwards? (A More Detailed Explanation)

Implementation (C++)

Code Explanation

Complexity

Tips and Common Mistakes

Quick Summary (for Students)

Visual DP Table (Step by Step)

Intuitive Visual Illustration — Blocks / Weights

Step 1: Initial State

Step 2: Add Weight 3

Step 3: Add Weight 4

Step 4: Add Weight 2

Conclusion

Subset Reconstruction — Which Numbers Make Up Each Sum?

Example

How to Fill the parent Table:

□ Reconstructing the Subset for T = 7

C++ Code for Tracking the Subset

Visual Illustration of Reconstruction

Problem Statement — Subset Sum

Input

Output

Note

Solution — Subset Sum (DP with Memoization)

Guide — Solution Idea

Base Cases

Why DP?

Top-down (Memoization)

Bottom-up (Tabulation)

Solution — C++ (top-down memoization)

Bottom-up Tabulation (Iterative)

Code Explanation

Example

Time and Space Complexity

NP-Completeness and Limitations of the DP Solution

Alternatives and Optimizations for Larger Values

Visualizing the Pseudopolynomial Growth of Subset Sum DP

Subset Sum — Visual Illustration of Subsets (Blocks / Weights)

Subset Sum — Subset Reconstruction

Solution Idea

C++ Code — Subset Reconstruction

Test Examples and Edge Cases

How Subset Reconstruction Works (Visual Explanation)

Example

DP Table (1 = Possible)

Marked take decisions

Backward Traversal (Reconstruction)

Why Does This Always Work?

Variants of the Subset Sum Problem

1. Subset Sum — The Basic Problem (YES / NO)

Problem Statement

Example

Guide

Solution — bottom-up (optimized)

Note

2. Subset Sum — Reconstructing a Solution

Problem Statement

Example

Guide

Solution — reconstruction from the 2D DP table

Note

3. Subset Sum — How Many Different Subsets Sum to T?

Problem Statement

Example

Guide

Marked `take` decisions