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 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
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.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- Decode Ways Medium Free How many letter strings could this digit string encode?
- House Robber II (Circular Street) Medium Free The street is a circle now - the first and last houses are neighbors.