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
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
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;
}

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