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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int compare(const void *a, const void *b) {
6 return *(int *)b - *(int *)a;
7}
8
9bool canPartition(int* nums, int numsSize, int k, int* subsetSums, int targetSubsetSum, int index) {
10 if (index == numsSize) return true;
11 for (int i = 0; i < k; i++) {
12 if (subsetSums[i] + nums[index] <= targetSubsetSum) {
13 subsetSums[i] += nums[index];
14 if (canPartition(nums, numsSize, k, subsetSums, targetSubsetSum, index + 1)) return true;
15 subsetSums[i] -= nums[index];
16 }
17 if (subsetSums[i] == 0) break; // Avoid trying same state again
18 }
19 return false;
20}
21
22bool canPartitionKSubsets(int* nums, int numsSize, int k) {
23 int totalSum = 0;
24 for (int i = 0; i < numsSize; i++) totalSum += nums[i];
25 if (totalSum % k != 0) return false;
26 int targetSubsetSum = totalSum / k;
27 qsort(nums, numsSize, sizeof(int), compare);
28 int* subsetSums = (int*)calloc(k, sizeof(int));
29 bool result = canPartition(nums, numsSize, k, subsetSums, targetSubsetSum, 0);
30 free(subsetSums);
31 return result;
32}
33
34int main() {
35 int nums[] = {4, 3, 2, 3, 5, 2, 1};
36 int k = 4;
37 int numsSize = sizeof(nums) / sizeof(nums[0]);
38 printf("%s\n", canPartitionKSubsets(nums, numsSize, k) ? "true" : "false");
39 return 0;
40}This solution begins by calculating the total sum of elements and checks early if this is divisible by k. It uses sorting to try larger numbers first, which helps in quicker pruning of impossible branches. The recursive function tries to add each number to the current subset sum and backtracks when necessary.
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.