This approach involves using backtracking to attempt to build k subsets, each with a sum equal to totalSum / k. The decision tree can be pruned by sorting the numbers in decreasing order and tracking the sums of the current subset.
Time Complexity: O(kn), where n is the number of elements, due to exploring all partition possibilities.
Space Complexity: O(n + k) due to recursive call stack and subset sums array.
1import java.util.Arrays;
2
3public class Solution {
4 public boolean canPartitionKSubsets(int[] nums, int k) {
5 int totalSum = 0;
6 for (int num : nums) totalSum += num;
7 if (totalSum % k != 0) return false;
8 int targetSubsetSum = totalSum / k;
9 Arrays.sort(nums);
10 return canPartition(nums, new int[k], nums.length - 1, targetSubsetSum);
11 }
12
13 private boolean canPartition(int[] nums, int[] subsetSums, int index, int targetSubsetSum) {
14 if (index < 0) return true;
15 int currVal = nums[index];
16 for (int i = 0; i < subsetSums.length; i++) {
17 if (subsetSums[i] + currVal <= targetSubsetSum) {
18 subsetSums[i] += currVal;
19 if (canPartition(nums, subsetSums, index - 1, targetSubsetSum)) return true;
20 subsetSums[i] -= currVal;
21 }
22 if (subsetSums[i] == 0) break;
23 }
24 return false;
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 int[] nums = {4, 3, 2, 3, 5, 2, 1};
30 int k = 4;
31 System.out.println(sol.canPartitionKSubsets(nums, k));
32 }
33}Java's implementation uses a similar DFS strategy, recursively attempting to place each number into one of the k capable 'buckets' (subset sums). Arrays.sort is utilized to facilitate efficient backtracking by hopping over impossible cases earlier.
A less intuitive but potentially powerful technique involves using bitmasking to represent subsets and top-down dynamic programming to evaluate the feasibility of partitioning. This uses state compression where each state represents a set of elements already partitioned; 1 means used, 0 means unused.
Time Complexity: O(n * 2n), determined by the states and transitions across the full bitmask.
Space Complexity: O(2n), which is used to store DP states for all subset configurations.
1import java.util.Arrays;
2
3public class Solution {
4 public boolean canPartitionKSubsets(int[] nums, int k) {
5 int totalSum = Arrays.stream(nums).sum();
6 if (totalSum % k != 0) return false;
7 int targetSubsetSum = totalSum / k;
8
9 int n = nums.length;
10 int[] dp = new int[1 << n];
11 Arrays.fill(dp, -1);
12 dp[0] = 0;
13
14 for (int mask = 0; mask < (1 << n); ++mask) {
15 if (dp[mask] == -1) continue;
16 for (int i = 0; i < n; ++i) {
17 if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= targetSubsetSum) {
18 int newMask = mask | (1 << i);
19 dp[newMask] = (dp[mask] + nums[i]) % targetSubsetSum;
20 }
21 }
22 }
23
24 return dp[(1 << n) - 1] == 0;
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 System.out.println(sol.canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4));
30 }
31}In this Java DP with bitmasking solution, bit shifts represent which numbers are in or out of a subset configuration. This method ensures each subset sum is proper modulo targetSubsetSum by using DP states. The state-mask expresses the current subset configuration as elements included or excluded.