Count subsets with a target sum

Challenge

Implement:

long long count_subsets_target(const int *a, int n, int target);

Return the number of subsets of the non-negative a[0..n-1] that sum to exactly target.

Input format

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

Output format

Number of subsets.

Constraints

Downward target sweep, adding counts.

Starter code

#include <stddef.h>
/* Number of subsets of a[0..n-1] (non-negative) whose elements sum to exactly target. target>=0. */
long long count_subsets_target(const int *a,int n,int target){ (void)a;(void)n;(void)target; return 0; }

Common mistakes

Using OR (reachability) instead of += (counting).

Edge cases to handle

target 0 -> 1 (the empty subset); a value of 0 doubles the count.

Background lessons

• Partition DP