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.
1from typing import List
2
3class Solution:
4 def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
5 total_sum = sum(nums)
6 if total_sum % k != 0:
7 return False
8 target_sum = total_sum // k
9 nums.sort(reverse=True)
10 subsets = [0] * k
11 return self.can_partition(nums, subsets, target_sum, 0)
12
13 def can_partition(self, nums: List[int], subsets: List[int], target: int, index: int) -> bool:
14 if index == len(nums):
15 return True
16 curr = nums[index]
17 for i in range(len(subsets)):
18 if subsets[i] + curr <= target:
19 subsets[i] += curr
20 if self.can_partition(nums, subsets, target, index + 1):
21 return True
22 subsets[i] -= curr
23 if subsets[i] == 0:
24 break
25 return False
26
27# Example usage:
28solution = Solution()
29print(solution.canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4))The Python approach also employs backtracking. Sorting the array before to ensure that larger numbers are considered first for the subsets aids in significantly cutting down on unnecessary recursive calls, improving the effective backtracking.
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.