Subset sum

Challenge

Implement:

int subset_sum(const int *a, int n, int target);

Return 1 if some subset of the non-negative a[0..n-1] sums exactly to target, else 0.

Input format

Non-negative a, count n, non-negative target.

Output format

1 if reachable, else 0.

Constraints

Downward target sweep (0/1 selection).

Starter code

#include <stddef.h>
/* Return 1 if some subset of a[0..n-1] (non-negative) sums exactly to target, else 0. target>=0. */
int subset_sum(const int *a,int n,int target){ (void)a;(void)n;(void)target; return 0; }

Common mistakes

Upward sweep allows reusing an element; use a downward loop.

Edge cases to handle

target 0 is always reachable (empty subset).

Background lessons

• 0/1 Knapsack & subset sum