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.
1using System;
2
3public class Solution {
4 public bool CanPartitionKSubsets(int[] nums, int k) {
5 int totalSum = 0;
6 foreach (var num in nums) totalSum += num;
7 if (totalSum % k != 0) return false;
8 int targetSubsetSum = totalSum / k;
9 Array.Sort(nums, (a, b) => b.CompareTo(a));
10 int[] subsetSums = new int[k];
11 return CanPartition(nums, subsetSums, targetSubsetSum, 0);
12 }
13
14 private bool CanPartition(int[] nums, int[] subsetSums, int targetSubsetSum, int index) {
15 if (index == nums.Length) return true;
16 for (int i = 0; i < subsetSums.Length; i++) {
17 if (subsetSums[i] + nums[index] <= targetSubsetSum) {
18 subsetSums[i] += nums[index];
19 if (CanPartition(nums, subsetSums, targetSubsetSum, index + 1)) return true;
20 subsetSums[i] -= nums[index];
21 }
22 if (subsetSums[i] == 0) break;
23 }
24 return false;
25 }
26
27 public static void Main() {
28 Solution sol = new Solution();
29 Console.WriteLine(sol.CanPartitionKSubsets(new int[] { 4, 3, 2, 3, 5, 2, 1 }, 4));
30 }
31}This C# solution wraps the backtracking method within the class structure of C#. Sorting in descending order and maintaining variable names consistent with numeric identifiers helps navigate potential unsolvable branches sooner.
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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4
5int dp[1 << 16], maskSum[1 << 16];
6
7bool canPartitionKSubsets(int* nums, int numsSize, int k) {
8 int totalSum = 0;
9 for (int i = 0; i < numsSize; ++i) totalSum += nums[i];
10 if (totalSum % k != 0) return false;
11 int targetSubsetSum = totalSum / k;
12
13 memset(dp, -1, sizeof(dp));
14 int allMask = (1 << numsSize) - 1;
15 dp[0] = 0;
16
17 // Traverse all states
18 for (int mask = 0; mask <= allMask; ++mask) {
19 if (dp[mask] == -1) continue;
20 for (int j = 0; j < numsSize; ++j) {
21 if (!(mask & (1 << j)) && dp[mask] + nums[j] <= targetSubsetSum) {
22 int newMask = mask | (1 << j);
23 dp[newMask] = (dp[mask] + nums[j]) % targetSubsetSum;
24 }
25 }
26 }
27
28 return dp[allMask] == 0;
29}
30
31int main() {
32 int nums[] = {4, 3, 2, 3, 5, 2, 1};
33 int k = 4;
34 int numsSize = sizeof(nums) / sizeof(nums[0]);
35 printf("%s\n", canPartitionKSubsets(nums, numsSize, k) ? "true" : "false");
36 return 0;
37}This approach encodes subsets using bitmasking where the nth bit represents the nth element in the nums array. Dynamic programming is used to store the remainder when each mask's subset sum is divided by targetSubsetSum. A successful partition is found when the full mask covers all elements with a remainder of 0.