Log inSign up
mediumLeetCodeNot Started

Partition to K Equal Sum Subsets

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1 · Valid 4-subset Partition:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true
Explanation: Total sum is 20, target sum per bucket is 5. It is possible to divide it into 4 subsets (5), (1, 4), (2, 3), (2, 3) with equal sums.

Example 2 · Invalid Partition:

Input: nums = [1, 2, 3, 4], k = 3
Output: false
Explanation: Total sum is 10, which is not divisible by 3.

Constraints:

  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 104
  • The frequency of each element is in the range [1, 4].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bucket-by-bucket sequential subset construction.
  • Learn Bitmask Dynamic Programming for NP-hard partitioning.
  • Apply symmetry pruning and duplicate element skipping.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Divide array into K subsets of equal sum
  • Small constraint N <= 16
  • Must use every element exactly once

Algorithmic Decision Tree:

  • Verify totalSum % k == 0 and nums[0] <= target.
  • Track used elements with boolean array visited or integer mask.
  • When currSum == target, call backtrack(k - 1, 0, 0) to build next subset.
  • Skip duplicate numbers with !visited[i - 1] && nums[i] == nums[i - 1].

Connected Patterns:

Matchsticks to SquarePartition Equal Subset SumCan I Win

1. Element-to-Bucket Backtracking (K^N)

Intuition

Maintain an array bucket[k]. For element idx, try placing into bucket 0..k-1. If bucket[j] + nums[idx] <= target, recurse on idx + 1. When idx == n, check if all buckets equal target.

When to apply: Simple baseline concept.

Algorithm

  1. In solve(idx):
  2. - If idx == n, check all buckets equal target.
  3. - For each bucket j from 0 to k - 1:
  4. - If bucket[j] + nums[idx] <= target:
  5. - bucket[j] += nums[idx].
  6. - Recurse solve(idx + 1).
  7. - bucket[j] -= nums[idx].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 bool solve(int idx, int k, int target, const vector<int>& nums, vector<int>& buckets) {
10 if (idx == nums.size()) {
11 for (int v : buckets) if (v != target) return false;
12 return true;
13 }
14
15 for (int j = 0; j < k; j++) {
16 if (buckets[j] + nums[idx] <= target) {
17 buckets[j] += nums[idx];
18 if (solve(idx + 1, k, target, nums, buckets)) return true;
19 buckets[j] -= nums[idx];
20 }
21 }
22 return false;
23 }
24
25public:
26 bool canPartitionKSubsets(vector<int>& nums, int k) {
27 int sum = accumulate(nums.begin(), nums.end(), 0);
28 if (sum % k != 0 || nums.size() < k) return false;
29 int target = sum / k;
30 vector<int> buckets(k, 0);
31 return solve(0, k, target, nums, buckets);
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> nums = {4, 3, 2, 3, 5, 2, 1};
38 cout << (sol.canPartitionKSubsets(nums, 4) ? "true" : "false") << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(K^N) — Branches K ways for each of the N numbers.
  • Space complexity: O(N + K) — Recursion stack depth N.

2. Bucket-by-Bucket Backtracking with Visited Array

Intuition

Instead of assigning elements to buckets, we construct bucket 1, then bucket 2, up to bucket k. When current bucket sum == target, recurse with k - 1, currSum = 0, start = 0.

When to apply: Standard intuitive interview backtracking solution.

Algorithm

  1. Sort nums descending.
  2. In backtrack(k, currSum, start):
  3. - If k == 1, return true (remaining elements must sum to target).
  4. - If currSum == target: return backtrack(k - 1, 0, 0).
  5. - For i from start to n - 1:
  6. - If !visited[i] && currSum + nums[i] <= target:
  7. - Mark visited, recurse backtrack(k, currSum + nums[i], i + 1), unmark.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 bool backtrack(int k, int currSum, int start, int target,
10 const vector<int>& nums, vector<bool>& visited) {
11 if (k == 1) return true; // Last subset automatically valid
12
13 if (currSum == target) {
14 return backtrack(k - 1, 0, 0, target, nums, visited);
15 }
16
17 for (int i = start; i < nums.size(); i++) {
18 if (!visited[i] && currSum + nums[i] <= target) {
19 visited[i] = true;
20 if (backtrack(k, currSum + nums[i], i + 1, target, nums, visited)) return true;
21 visited[i] = false; // backtrack
22 }
23 }
24 return false;
25 }
26
27public:
28 bool canPartitionKSubsets(vector<int>& nums, int k) {
29 int sum = accumulate(nums.begin(), nums.end(), 0);
30 if (sum % k != 0 || nums.size() < k) return false;
31 int target = sum / k;
32
33 sort(nums.rbegin(), nums.rend());
34 if (nums[0] > target) return false;
35
36 vector<bool> visited(nums.size(), false);
37 return backtrack(k, 0, 0, target, nums, visited);
38 }
39};
40
41int main() {
42 Solution sol;
43 vector<int> nums = {4, 3, 2, 3, 5, 2, 1};
44 cout << (sol.canPartitionKSubsets(nums, 4) ? "true" : "false") << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(K * 2^N) — Traverses subsets for each bucket.
  • Space complexity: O(N) — Visited array and call stack take O(N).

3. Bitmask DP / Memoized State Space Search (Optimal)

Intuition

The state is fully captured by the bitmask of used numbers. If two different orderings of selections produce the same mask, they have identical remainder dp[mask] = (dp[prevMask] + nums[i]) % target. Using a memo table of size 1 << N eliminates all redundant search paths.

When to apply: The optimal guaranteed O(N * 2N) state space solution.

Algorithm

  1. Check totalSum % k == 0 and nums[0] <= target.
  2. Initialize dp array of size 1 << N with -1. dp[0] = 0.
  3. For mask from 0 to (1 << N) - 1:
  4. - If dp[mask] == -1, continue.
  5. - For each unvisited bit i:
  6. - If (dp[mask] % target) + nums[i] <= target:
  7. - dp[mask | (1 << i)] = dp[mask] + nums[i].
  8. Return dp[(1 << N) - 1] == totalSum.

K-Subset Sequential Construction Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Sorted descending: [5, 4, 3, 3, 2, 2, 1]
Visual state
Values and pointers at this exact step
array
S
Empty (0/5)
Empty (0/5)
Empty (0/5)
Empty (0/5)
0
1
2
3
Variables at this step
target
5
kLeft
4
Why this step matters

Sorted descending: [5, 4, 3, 3, 2, 2, 1]. Target sum per subset is 5.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 bool canPartitionKSubsets(vector<int>& nums, int k) {
11 int n = nums.size();
12 int sum = accumulate(nums.begin(), nums.end(), 0);
13 if (sum % k != 0 || n < k) return false;
14 int target = sum / k;
15
16 sort(nums.rbegin(), nums.rend());
17 if (nums[0] > target) return false;
18
19 vector<int> dp(1 << n, -1);
20 dp[0] = 0;
21
22 for (int mask = 0; mask < (1 << n); mask++) {
23 if (dp[mask] == -1) continue;
24
25 for (int i = 0; i < n; i++) {
26 if (!(mask & (1 << i))) {
27 if ((dp[mask] % target) + nums[i] <= target) {
28 dp[mask | (1 << i)] = dp[mask] + nums[i];
29 }
30 }
31 }
32 }
33
34 return dp[(1 << n) - 1] == sum;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> nums = {4, 3, 2, 3, 5, 2, 1};
41 cout << (sol.canPartitionKSubsets(nums, 4) ? "true" : "false") << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Evaluates 2N bitmask states with N transitions each.
  • Space complexity: O(2^N) — DP table of size 2N.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Element-to-Bucket BacktrackingO(K^N)O(N + K)Place each element into one of the k buckets.K-way branching per element
2.Bucket-by-Bucket Backtracking with Visited ArrayO(K * 2^N)O(N)Fill bucket 1, then bucket 2, up to bucket k sequentially.Revisiting identical sub-masks
3.Bitmask DP / Memoized State Space SearchOptimalO(N * 2^N)O(2^N)Memoize subset bitmasks in DP table.2N table size

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Starting search from start = 0 inside the same bucket (which allows duplicate permutations of elements within the same bucket).

Pitfall 2:

Missing the k == 1 early termination base case.

Crucial Edge Cases to Validate:

  • k = 1: Single subset is always true.
  • k = N: Valid only if all elements are equal.
  • Total Sum not divisible by k: returns false immediately.
  • Max element > target: returns false immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain the two dimensions of symmetry: symmetry within a bucket (avoided by start = i + 1) and symmetry across buckets (avoided by sequential bucket construction).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is building subsets bucket-by-bucket faster than assigning elements to buckets?

2.When k == 1 in bucket-by-bucket recursion, why can we immediately return true?

Back to DSA Sheet