Partition to K Equal Sum Subsets
Solve this Problemnums 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.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ k ≤ nums.length ≤ 16 - ◆
1 ≤ nums[i] ≤ 10000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Bucket Assignment
BruteKeep k running bucket totals, all starting at 0. Walk the numbers one at a time, and for each one, try dropping it into every bucket that wouldn't push that bucket over the target — recursing after each attempt, undoing it if that path fails. Correct, but nothing here prevents trying a number in two buckets that already hold the exact same running total: both attempts are guaranteed to play out identically, yet both get explored anyway.
O(kⁿ)O(n) recursion depth1class Solution {
2 public boolean canPartitionKSubsets(int[] nums, int k) {
3 int sum = 0;
4 for (int num : nums) {
5 sum += num;
6 }
7 if (sum % k != 0) return false;
8 int target = sum / k;
9 int[] buckets = new int[k];
10 return backtrack(nums, 0, buckets, target);
11 }
12
13 private boolean backtrack(int[] nums, int idx, int[] buckets, int target) {
14 if (idx == nums.length) return true;
15 for (int i = 0; i < buckets.length; i++) {
16 if (buckets[i] + nums[idx] > target) continue;
17 buckets[i] += nums[idx];
18 if (backtrack(nums, idx + 1, buckets, target)) return true;
19 buckets[i] -= nums[idx];
20 }
21 return false;
22 }
23}Optimal — Backtracking With Pruning
OptimalTwo small changes eliminate most of the wasted exploration. First, sort the numbers largest-first, so the pickiest placements happen early — a large number has fewer buckets it can legally fit into, and if none of them work there's no point discovering that after wasting time placing every small number first. Second, skip trying a number in any bucket whose running total exactly matches a bucket already tried and failed at this step — those two attempts are provably identical, so only the first one needs to run.
O(kⁿ) worst case, heavily prunedO(n) recursion depth1class Solution {
2 public boolean canPartitionKSubsets(int[] nums, int k) {
3 int sum = 0;
4 for (int num : nums) {
5 sum += num;
6 }
7 if (sum % k != 0) return false;
8 int target = sum / k;
9 Integer[] sorted = new Integer[nums.length];
10 for (int i = 0; i < nums.length; i++) sorted[i] = nums[i];
11 Arrays.sort(sorted, Collections.reverseOrder());
12 if (sorted[0] > target) return false;
13 int[] buckets = new int[k];
14 return backtrack(sorted, 0, buckets, target);
15 }
16
17 private boolean backtrack(Integer[] nums, int idx, int[] buckets, int target) {
18 if (idx == nums.length) return true;
19 for (int i = 0; i < buckets.length; i++) {
20 if (buckets[i] + nums[idx] > target) continue;
21 if (i > 0 && buckets[i] == buckets[i - 1]) continue;
22 buckets[i] += nums[idx];
23 if (backtrack(nums, idx + 1, buckets, target)) return true;
24 buckets[i] -= nums[idx];
25 }
26 return false;
27 }
28}