Subset Sum

Subset sum asks whether some 0/1 subset reaches an exact target, not the best value under a capacity. Boolean states merge histories with the same sum. We also recover one witness using frozen first-reach parent links. Nonnegative inputs make a bounded target array and descending update order possible; arbitrary negative values need a different range representation.

Prerequisites: 0/1 Knapsack; reconstruction; boolean states.

Build the idea

1. Recognize the repeated subproblems

   Complete search tries 2^n subsets. When target S is moderate and values are nonnegative, there are only S+1 relevant totals; sums above S can never return downward. Constraints n≤1000, S≤100000 permit an O(nS) pseudo-polynomial method. With negative values, discarding larger sums would be unsound because a later negative could bring them back.

2. Define the state

   reachable[s] means some subset of processed entries totals exactly s. item[s] and previous[s] record the input index used and its prior sum when s becomes reachable for the first time. The zero sum is reachable by the empty subset, including when the input contains zeros. We need just one witness, not the number of subsets.

3. Derive the transition

   For each value x, scan s downward from S to x. If s was not reachable but s−x was, set it reachable and freeze parent data. Descending order ensures the predecessor has not newly used this item. An x>S causes no updates. For x=0 no new false state can become true from itself, so no zero-length parent cycle is created.

   $$\mathrm{reachable}\left[s\right]=\mathrm{reachable}\left[s\right]\mathrm{OR}\mathrm{reachable}[s-x]$$

4. Base cases and computation order

   Initialize reachable[0]=true and all other entries false. Read all items even if the target is already reachable, keeping the input contract simple. If target remains false, print NO. Otherwise follow previous from S until zero, collect item IDs and reverse. Frozen parent states were reached with strictly earlier items; zero values are never needed to create a new positive witness sum.

5. Correctness and invariant

   For each item, a target subset either excludes it or removes it to a subset of earlier entries totaling s−x. Boolean OR therefore covers exactly all feasible subsets. First-reach parent data points to that earlier-layer witness and is never overwritten, so its chain uses no input item twice. This freezing matters: an arbitrary mutable parent scheme on compressed DP can reference inconsistent layers.

6. Work the example

   Values [3,34,4,5], target 9: after the first item sums {0,3} are reachable;34 is too large. Adding 4 yields {0,3,4,7}. Adding 5 reaches 9 from 4, storing item 4 and predecessor 4, whose parent uses item 3. Output YES and IDs 3,4 witnesses 4+5.

   processed values	relevant reachable sums
   none	0
   3	0,3
   3,34,4	0,3,4,7
   all	0,3,4,5,7,8,9

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,target;
    std::cin>>n>>target;
    std::vector<bool>reachable(target+1);
    std::vector<int>item(target+1,-1),previous(target+1,-1);
    reachable[0]=true;
    for(int i=1;i<=n;++i){
        int x;
        std::cin>>x;
        for(int s=target;s>=x;--s){
            if(!reachable[s]&&reachable[s-x]){
                reachable[s]=true;
                item[s]=i;
                previous[s]=s-x;
            }
        }
    } // Freeze the first parent for each sum.
    if(!reachable[target]){
        std::cout<<"NO\n";
        return 0;
    }
    std::vector<int>chosen;
    for(int s=target;s>0;s=previous[s]){
        chosen.push_back(item[s]);
    }
    std::reverse(chosen.begin(),chosen.end());
    std::cout<<"YES\n"<<chosen.size();
    for(int id:chosen){
        std::cout<<' '<<id;
    }
    std::cout<<'\n';
}

Complexity analysis

O(nS) time, O(S) reachability/parent space and O(n) worst-case witness storage. The logical item layers are compressed through descending sums. Bitset shifts can accelerate decision-only nonnegative variants, but direct reconstruction needs more care.

Example input and output

Read n S (0≤n≤1000,0≤S≤100000), then n values in 0..10^6. Print NO, or YES followed by witness count and 1-based item IDs. Empty target permits an empty subset.

Input

4 9
3 34 4 5

Output

YES
2 3 4

Values [3,34,4,5], target 9: after the first item sums {0,3} are reachable;34 is too large. Adding 4 yields {0,3,4,7}. Adding 5 reaches 9 from 4, storing item 4 and predecessor 4, whose parent uses item 3. Output YES and IDs 3,4 witnesses 4+5.

Practical applications

Use exact nonnegative sum feasibility and partition reductions. Meet-in-the-middle helps when n is small and S huge; offset/range maps may support negative inputs under suitable bounds. Counting subsets requires counts and multiplicity rules rather than a boolean.

Check your understanding

Why can values above S be ignored in this implementation?

Put it into practice

Test zeros, duplicate values, S=0 and an unreachable positive target.