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.
1function canPartitionKSubsets(nums, k) {
2 const totalSum = nums.reduce((a, b) => a + b, 0);
3 if (totalSum % k !== 0) return false;
4 const targetSubsetSum = totalSum / k;
5 nums.sort((a, b) => b - a);
6 const subsetSums = new Array(k).fill(0);
7 return canPartition(nums, subsetSums, targetSubsetSum, 0);
8
9 function canPartition(nums, subsetSums, target, index) {
10 if (index === nums.length) return true;
11 for (let i = 0; i < subsetSums.length; i++) {
12 if (subsetSums[i] + nums[index] <= target) {
13 subsetSums[i] += nums[index];
14 if (canPartition(nums, subsetSums, target, index + 1)) return true;
15 subsetSums[i] -= nums[index];
16 }
17 if (subsetSums[i] === 0) break;
18 }
19 return false;
20 }
21}
22
23console.log(canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4));The JavaScript function operates on a direct algorithm similar to the provided Python implementation, using inline functions for clarity. Sorting aids in checking larger number placements first, helping with backtracking and efficiency.
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 <vector>
2#include <cstring>
3
4class Solution {
5public:
6 bool canPartitionKSubsets(std::vector<int>& nums, int k) {
7 int totalSum = 0, n = nums.size();
8 for (int num : nums) totalSum += num;
9 if (totalSum % k != 0) return false;
10 int targetSubsetSum = totalSum / k;
11
12 std::vector<int> dp(1 << n, -1);
13 dp[0] = 0;
14
15 for (int mask = 0; mask < (1 << n); ++mask) {
16 if (dp[mask] == -1) continue;
17 for (int i = 0; i < n; ++i) {
18 if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= targetSubsetSum) {
19 int newMask = mask | (1 << i);
20 dp[newMask] = (dp[mask] + nums[i]) % targetSubsetSum;
21 }
22 }
23 }
24
25 return dp[(1 << n) - 1] == 0;
26 }
27};In this C++ solution, the DP array uses a bitmask to effectively explore the use of each element, dynamically calculating subset fits without redundancy. The key is recognizing when the current mask configuration totals to a valid subset sum by looking at remainders.