Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4,3,2,3,5,2,1], k = 4 Output: true Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2:
Input: nums = [1,2,3,4], k = 3 Output: false
Constraints:
1 <= k <= nums.length <= 161 <= nums[i] <= 104[1, 4].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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
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.
| Approach | Complexity |
|---|---|
| Backtracking with Target Subset Sum | Time Complexity: O(kn), where n is the number of elements, due to exploring all partition possibilities. |
| Dynamic Programming and State Compression | Time Complexity: O(n * 2n), determined by the states and transitions across the full bitmask. |
DP 15. Partition Equal Subset Sum | DP on Subsequences • take U forward • 262,594 views views
Watch 9 more video solutions →Practice Partition to K Equal Sum Subsets with our built-in code editor and test cases.
Practice on FleetCode