Problem

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.

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3
4

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

Variants

K = 2 ⇨ 2-Partition Problem

We have covered this problem for k = 2 here: Partition Equal Subset Sum.

K = 3 ⇨ 3-Partition Problem

This problem occurred as Partitioning Souveniers Problem in the sixth week of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego. We will solve it generically here in this problem.

Similar Problems

Solution

Method 1 - Backtracking

We can use visited boolean array to track if the value is part of some subset. Then we go deeper into DFS. For each partition, targetSum is sum(nums)/k.

Base Case

  • if we reach k = 1, then we have reached target
  • if currSum > targetSum then we return false

Actual Recursion

  • If we currSum is targetSum, and there are k's more than 1, then we find the targetSum again with k - 1 partition.
  • If not, go through array and see if we can find k partitions and backtrack if we couldn’t find answer in that path

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// C++ backtracking solution
#include <vector>
#include <numeric>

class Solution {
public:
	bool canPartitionKSubsets(std::vector<int>& nums, int k) {
		int n = nums.size();
		int sum = std::accumulate(nums.begin(), nums.end(), 0);
		if (sum % k != 0) return false;
		int target = sum / k;
		std::vector<bool> used(n, false);
		return dfs(nums, used, k, 0, 0, target);
	}

private:
	bool dfs(const std::vector<int>& nums, std::vector<bool>& used, int k, int start, int currSum, int target) {
		if (k == 1) return true;
		if (currSum == target) return dfs(nums, used, k - 1, 0, 0, target);
		for (int i = start; i < (int)nums.size(); ++i) {
			if (used[i]) continue;
			if (currSum + nums[i] > target) continue;
			used[i] = true;
			if (dfs(nums, used, k, i + 1, currSum + nums[i], target)) return true;
			used[i] = false;
		}
		return false;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public boolean canPartitionKSubsets(int[] nums, int k) {
	var sum = IntStream.of(nums).sum();
	if (sum % k != 0) {
		return false;
	}
	return canPartitionKSubsets(nums, k, 0, 0, sum / k, new boolean[nums.length]);

}

private boolean canPartitionKSubsets(int[] nums, int k, int start, int currSum, final int targetSum, boolean[] visited) {
	if (k == 1) {
		return true;
	}
	if (currSum > targetSum) {
		return false;
	}
	if (currSum == targetSum) {
		return canPartitionKSubsets(nums, k - 1, 0, 0, targetSum, visited);
	}
	for (var i = start; i < nums.length; i++) {
		if (visited[i]) {
			continue;
		}
		visited[i] = true;
		if (canPartitionKSubsets(nums, k, i + 1, currSum + nums[i], targetSum, visited)) {
			return true;
		}
		visited[i] = false;
	}
	return false;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from typing import List

class Solution:
	def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
		n = len(nums)
		s = sum(nums)
		if s % k != 0:
			return False
		target = s // k
		used = [False] * n

		def dfs(k_remain: int, start: int, curr_sum: int) -> bool:
			if k_remain == 1:
				return True
			if curr_sum == target:
				return dfs(k_remain - 1, 0, 0)
			for i in range(start, n):
				if used[i] or curr_sum + nums[i] > target:
					continue
				used[i] = True
				if dfs(k_remain, i + 1, curr_sum + nums[i]):
					return True
				used[i] = False
			return False

		return dfs(k, 0, 0)

Complexity

  • ⏰ Time complexity: O(k*2^n) because we run k iterations for recursion, and in that we have 2^n choices to create the subset such that sum is equal to sum(nums)/k.
  • 🧺 Space complexity: O(n) for visited set, recursion stack, etc

Method 2 - Bitmask DP (DP over subsets)

Intuition

We can encode which elements are used using a bitmask and use DP to track the current modulo-sum of the partially filled subsets. This allows us to avoid the extra factor of k in the naive backtracking by reusing computed subset-fillability information for every mask.

Approach

  1. Compute total sum and target = sum / k. If sum % k != 0, return false.
  2. Let dp[mask] = true if the subset represented by mask can be partitioned into some number of full buckets and a residual sum less than or equal to target; we also track the current modulo-sum for that mask.
  3. Iterate masks from 0..(1«n)-1 and try to add an unused element to extend the mask if it doesn’t overflow the target.
  4. If dp[(1«n)-1] is reachable and completes exactly k buckets, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
	bool canPartitionKSubsets(vector<int>& nums, int k) {
		int n = nums.size();
		int sum = accumulate(nums.begin(), nums.end(), 0);
		if (sum % k) return false;
		int target = sum / k;
		int N = 1 << n;
		vector<int> dp(N, -1); // -1 = unreachable, otherwise stores current bucket sum modulo target
		dp[0] = 0;
		for (int mask = 0; mask < N; ++mask) {
			if (dp[mask] < 0) continue;
			for (int i = 0; i < n; ++i) if (!(mask & (1 << i))) {
				int nxt = mask | (1 << i);
				if (dp[mask] + nums[i] <= target) {
					dp[nxt] = max(dp[nxt], (dp[mask] + nums[i]) % target);
				}
			}
		}
		return dp[N-1] == 0;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from typing import List

class Solution:
	def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
		n = len(nums)
		s = sum(nums)
		if s % k != 0:
			return False
		target = s // k
		N = 1 << n
		dp = [-1] * N
		dp[0] = 0
		for mask in range(N):
			if dp[mask] < 0:
				continue
			for i in range(n):
				if not (mask >> i) & 1:
					nxt = mask | (1 << i)
					if dp[mask] + nums[i] <= target:
						dp[nxt] = max(dp[nxt], (dp[mask] + nums[i]) % target)
		return dp[N-1] == 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
	public boolean canPartitionKSubsets(int[] nums, int k) {
		int n = nums.length;
		int sum = 0;
		for (int x : nums) sum += x;
		if (sum % k != 0) return false;
		int target = sum / k;
		int N = 1 << n;
		int[] dp = new int[N];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		for (int mask = 0; mask < N; ++mask) {
			if (dp[mask] < 0) continue;
			for (int i = 0; i < n; ++i) if ((mask & (1 << i)) == 0) {
				int nxt = mask | (1 << i);
				if (dp[mask] + nums[i] <= target) {
					dp[nxt] = Math.max(dp[nxt], (dp[mask] + nums[i]) % target);
				}
			}
		}
		return dp[N-1] == 0;
	}
}

Complexity

  • ⏰ Time complexity: O(n * 2^n) – we process each subset mask and attempt to add up to n elements.
  • 🧺 Space complexity: O(2^n) – the DP table stores one entry per subset mask.
Caveat

Bitmask DP uses O(2^n * n) time and O(2^n) space, so it’s only practical up to n ~ 16-20 depending on constraints.