Partition to K Equal Sum Subsets

Implement canPartitionKSubsets

Can the numbers in nums be sorted into exactly k non-empty groups so that every group's numbers add up to the exact same total? That's the question to answer — yes or no. If the array's total sum doesn't divide evenly by k, the answer is immediately no — there's no target total to aim for. Otherwise, this comes down to trying to fill k running totals to that shared target, one number at a time, backing out of any placement that turns out not to work.

Example 1:

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

Output: true

Example 2:

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

Output: false

Example 3:

Input: nums = [1], k = 1

Output: true

+ 10 hidden test cases run on Submit.

Constraints:

  • 1 ≤ k ≤ nums.length ≤ 16
  • 1 ≤ nums[i] ≤ 10000

nums =

[4, 3, 2, 3, 5, 2, 1]

k =

4