Skip to content
Katabench
Try free

Partition Equal Subset Sum

Medium About 25 min Free, no account needed

Can the array split into two halves of equal sum?

The brief

Given an array of positive integers nums, return true if it can be split into two subsets with equal sums.

The performance bar

The obvious approach branches include/exclude on every element, 2^n. The hidden test has 200 elements, so the exponential branching is far too slow. Note that the two subsets must each sum to half the total, and you will need an approach that runs in time proportional to the element count times that target sum, not exponential in the element count.

Starter code

C#
using System;

public class Solution
{
    // TODO: return true when nums splits into two equal-sum subsets.
    public bool CanPartition(int[] nums)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Related katas