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

a is array of n positive integers.

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

Assuming sorted array or integer overflow on total sum.

Edge cases to handle

Odd sum (impossible), empty array, single element, partition exists.

Background lessons

• Partition DP