Count size-k subsets with a target sum

Challenge

Implement:

int count_k_subset_sum(const int *a, int n, int k, int target);

Count subsets of exactly k elements of the non-negative a[0..n-1] that sum to target, via backtracking.

Input format

Non-negative a, n, k, target.

Output format

Number of qualifying subsets.

Constraints

Prune when not enough elements remain.

Starter code

#include <stddef.h>
/* Count subsets of EXACTLY k elements of a[0..n-1] (non-negative) that sum to target, via backtracking. */
int count_k_subset_sum(const int *a,int n,int k,int target){ (void)a;(void)n;(void)k;(void)target; return 0; }

Common mistakes

Forgetting the size constraint (that's plain subset-sum); not pruning.

Edge cases to handle

k==0 counts 1 iff target==0.

Background lessons

• Combinations & subset search