Partition to K Equal Sum Subsets

Problem

Given an integer array nums and an integer k, return true if nums can be split into k non-empty subsets whose sums are all equal. Every element must belong to exactly one subset.

Constraints

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

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def canPartitionKSubsets(self, nums, k):
        total = sum(nums)
        if total % k:
            return False
        target = total // k
        nums.sort(reverse=True)
        if nums[0] > target:
            return False
        used = [False] * len(nums)
        def bt(count, cur, start):
            if count == k:
                return True
            if cur == target:
                return bt(count + 1, 0, 0)
            for i in range(start, len(nums)):
                if used[i] or cur + nums[i] > target:
                    continue
                used[i] = True
                if bt(count, cur + nums[i], i + 1):
                    return True
                used[i] = False
            return False
        return bt(0, 0, 0)

Java

import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (k <= 0 || sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums);
        // The largest element cannot exceed a single bucket.
        if (nums[nums.length - 1] > target) return false;
        boolean[] used = new boolean[nums.length];
        return build(nums, used, nums.length - 1, 0, target, k);
    }

    // Fill one bucket at a time. cur is the running sum of the bucket
    // currently being filled; k buckets still need completing.
    private boolean build(int[] nums, boolean[] used, int idx,
                          int cur, int target, int k) {
        if (k == 1) return true;                 // last bucket auto-balances
        if (cur == target) {
            return build(nums, used, nums.length - 1, 0, target, k - 1);
        }
        for (int i = idx; i >= 0; i--) {
            if (used[i] || cur + nums[i] > target) continue;
            used[i] = true;
            if (build(nums, used, i - 1, cur + nums[i], target, k)) return true;
            used[i] = false;
            // Skip equal values — re-trying them explores the same branch.
            while (i > 0 && nums[i - 1] == nums[i]) i--;
        }
        return false;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.