Equal-sum partition

Challenge

Implement:

int can_partition(const int *a, int n);

Return 1 if the non-negative array can be split into two subsets with equal sums, else 0.

Input format

Non-negative a, count n.

Output format

1 if an equal split exists, else 0.

Constraints

Only possible when the total is even.

Starter code

#include <stddef.h>
/* Return 1 if a[0..n-1] (non-negative) can be split into two subsets with equal sums, else 0. */
int can_partition(const int *a,int n){ (void)a;(void)n; return 0; }

Common mistakes

Not short-circuiting on an odd total (there is no half to hit).

Edge cases to handle

Odd total -> 0.

Background lessons

• Partition DP