DP — Partition to K Equal Sum Subsets

↗ LeetCode: Partition to K Equal Sum Subsets · Medium · pattern chapter →

Asked atMetaAmazonGoogle

Split nums into k subsets each summing to total/k.

Example 1 — nums=[4,3,2,3,5,2,1], k=4 → trueExample 2 — nums=[1,2,3,4], k=3 → false

Constraints — 1 ≤ n ≤ 16. Brute enumerates k^n partitions — at n=16, k=4 that's 4·10⁹ ops (borderline TLE). Bitmask DP + prune is O(k·2ⁿ) = 4·65536 ≈ 2·10⁶ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Backtracking with sort-desc + pruning

Sort desc; place each into buckets; skip mirrored-empty.

Approach 2 — Bitmask DP (canonical for n ≤ 16)

Insight. dp[mask] = min "leftover" sum of current bucket after using mask elements. Transition: try adding each unused element if it fits.

java

boolean canPartitionKSubsets(int[] nums, int k) {
    int total = 0; for (int x : nums) total += x;
    if (total % k != 0) return false;
    int target = total / k;
    int n = nums.length, full = 1 << n;
    int[] dp = new int[full];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int mask = 0; mask < full; mask++) {
        if (dp[mask] < 0) continue;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) continue;
            if (dp[mask] + nums[i] > target) continue;
            int nm = mask | (1 << i);
            dp[nm] = (dp[mask] + nums[i]) % target;
        }
    }
    return dp[full - 1] == 0;
}

Execution Trace

Backtracking with sort-desc + pruning

Step 1 / 3Initialize scan.

Complexity — Time O(n · 2ⁿ); Space O(2ⁿ).

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Backtracking + sort desc	worst exp	O(k)	works
Bitmask DP	O(n · 2ⁿ)	O(2ⁿ)	canonical for n ≤ 16

When to use which

n ≤ 16 → bitmask DP.
Larger n → backtracking with heavy pruning.
k=2 → simpler Partition Equal Subset Sum.

✨AI Study CompanionBeta

Was this page helpful?

DP — Partition to K Equal Sum Subsets ​

Approach 1 — Backtracking with sort-desc + pruning ​

Approach 2 — Bitmask DP (canonical for n ≤ 16) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​