All problems

Partition to K Equal Sum Subsets

Medium · backtracking

You are given a list nums of positive integers and a number k. Split the numbers into exactly k groups so that every number is in exactly one group and all k groups have the same sum. The order of the numbers inside a group does not matter.

Return true if such a split exists, and false otherwise.

Examples

Example 1

Input: nums = [3, 3, 2, 1, 1, 2], k = 3

Output: true

Each group can add up to 4: [3, 1], [3, 1] and [2, 2].

Example 2

Input: nums = [1, 2, 3, 4, 5], k = 2

Output: false

The total is 15, which cannot be split into two equal whole sums.

Example 3

Input: nums = [5, 5, 5, 5, 5, 1], k = 2

Output: false

The total is 26, so each group needs 13, but a group of these numbers adds up to 11 or 15 and never 13.

Constraints