Partition to K Equal Sum Subsets

Med

#0652Time: O(k^N). For each of the `N` numbers in the input array, we explore `k` possibilities (placing it in one of the `k` subsets). This leads to a time complexity that is exponential in `N`.Space: O(N + k). The recursion depth can go up to `N`, contributing `O(N)` to the space complexity for the call stack. We also use an auxiliary array of size `k` to store the sums of the subsets.2 companies

Patterns

Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

Data structures

Array

Companies

ByteDance LinkedIn

Prompt

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 <= 16
1 <= nums[i] <= 10⁴
The frequency of each element is in the range [1, 4].

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward brute-force backtracking algorithm. The core idea is to try and place each number from the input array nums into one of the k available subsets. The recursion explores every possible assignment of numbers to subsets until a valid partition is found or all possibilities are exhausted.

Algorithm

Calculate the total sum of nums. If it's not divisible by k, or if k is non-positive, return false.
Calculate the targetSum for each subset, which is totalSum / k.
Sort the input array nums in descending order. This is an optimization that helps in pruning the search space faster by trying to place larger numbers first.
Create an array subsetSums of size k to keep track of the current sum of each of the k subsets, initialized to all zeros.
Implement a recursive backtracking function, say backtrack(index), which tries to place the number nums[index].
Base Case: If index equals nums.length, it means all numbers have been successfully placed into subsets, so we return true.
Recursive Step: For the number nums[index], iterate through the k subsets. For each subset j, if adding nums[index] does not exceed targetSum:
- Add nums[index] to subsetSums[j].
- Make a recursive call backtrack(index + 1).
- If the recursive call returns true, a solution is found, so propagate true.
- If not, backtrack by subtracting nums[index] from subsetSums[j] and try the next subset.
An important optimization: If placing nums[index] into an empty subset j (where subsetSums[j] == 0) fails, we can stop trying to place it in any other empty subset, as it would lead to a symmetric, failing search path.
If the loop finishes without finding a suitable subset for nums[index], return false.
The initial call to start the process is backtrack(0).

Walkthrough

In this method, we first perform some preliminary checks. The total sum of all numbers in nums must be perfectly divisible by k; otherwise, it's impossible to form k subsets with equal sums. The required sum for each subset is targetSum = totalSum / k. Additionally, no single number can be larger than this targetSum.

The main logic resides in a recursive function that takes the current index of the number to be placed as an argument. This function iterates through the k subsets and attempts to add the current number to one of them. If adding the number doesn't violate the targetSum constraint, it makes a recursive call for the next number. If the subsequent recursive call finds a solution, we're done. If not, we backtrack by removing the number and trying the next available subset.

To make this brute-force approach slightly more tenable, we can introduce optimizations. Sorting the input array nums in descending order is a powerful heuristic. By attempting to place larger numbers first, we are more likely to hit the targetSum constraint early, which helps to prune the search tree and reduce the number of recursive calls.

1import java.util.Arrays;2 3class Solution {4    public boolean canPartitionKSubsets(int[] nums, int k) {5        int totalSum = 0;6        for (int num : nums) {7            totalSum += num;8        }9        if (k <= 0 || totalSum % k != 0) {10            return false;11        }12        int targetSum = totalSum / k;13        14        // Sort in descending order for optimization15        Arrays.sort(nums);16        for(int i = 0, j = nums.length - 1; i < j; i++, j--){17            int temp = nums[i];18            nums[i] = nums[j];19            nums[j] = temp;20        }21        22        if (nums[0] > targetSum) return false;23 24        return backtrack(nums, 0, new int[k], targetSum);25    }26 27    private boolean backtrack(int[] nums, int index, int[] subsetSums, int targetSum) {28        if (index == nums.length) {29            return true;30        }31 32        int currentNum = nums[index];33        for (int i = 0; i < subsetSums.length; i++) {34            if (subsetSums[i] + currentNum <= targetSum) {35                subsetSums[i] += currentNum;36                if (backtrack(nums, index + 1, subsetSums, targetSum)) {37                    return true;38                }39                subsetSums[i] -= currentNum; // Backtrack40                // Optimization: If this subset was empty, and it failed, 41                // no need to try other empty subsets.42                if (subsetSums[i] == 0) break;43            }44        }45        return false;46    }47}

Complexity

Time

O(k^N). For each of the `N` numbers in the input array, we explore `k` possibilities (placing it in one of the `k` subsets). This leads to a time complexity that is exponential in `N`.

Space

O(N + k). The recursion depth can go up to `N`, contributing `O(N)` to the space complexity for the call stack. We also use an auxiliary array of size `k` to store the sums of the subsets.

Trade-offs

Pros

Conceptually simple and relatively easy to understand and implement.
It correctly solves the problem for small input sizes.

Cons

Extremely inefficient with a time complexity of O(k^N), making it impractical for anything but very small inputs.
The search space grows exponentially with both N and k.

This approach refines the backtracking strategy. Instead of assigning each number to one of k buckets, we try to build each of the k subsets one by one. The algorithm searches for a combination of unused numbers that sum up to the target value. Once a valid subset is found, it's conceptually 'removed', and the algorithm recursively searches for the next subset among the remaining numbers. This method allows for more effective pruning.

Algorithm

Perform the same initial checks: calculate totalSum and targetSum. Return false if partitioning is impossible.
Sort the nums array. This is crucial for optimizations. We will iterate from largest to smallest.
Use a boolean array used of size N to keep track of numbers that have already been placed in a subset.
Define a recursive function backtrack(k, currentSum, startIndex) where k is the number of subsets we still need to form.
Base Case 1: If k == 0, it means we have successfully formed all k subsets. Return true.
Base Case 2: If currentSum == targetSum, we have just completed one subset. We then need to form k-1 more subsets from the remaining numbers. We do this by making a recursive call: backtrack(k - 1, 0, nums.length - 1).
Recursive Step: Iterate through the numbers from startIndex down to 0 (from largest to smallest).
- If nums[i] is not used and adding it to currentSum does not exceed targetSum:
  - Mark nums[i] as used.
  - Recursively call backtrack(k, currentSum + nums[i], i - 1).
  - If the call returns true, a solution is found, so return true.
  - If not, backtrack by un-marking nums[i] as used.
- To avoid redundant computations with duplicate numbers, if nums[i] is the same as nums[i+1] and the path with nums[i+1] failed (i.e., used[i+1] is false), we can skip nums[i].
The initial call is backtrack(k, 0, nums.length - 1).

Walkthrough

The core idea is to change the perspective of the search. We aim to find k disjoint subsets, each summing to targetSum. The recursive function tries to build one such subset. When a subset is successfully formed (its sum equals targetSum), the function is called again to find the remaining k-1 subsets from the pool of unused numbers.

A boolean array used is maintained to mark which numbers have been assigned to a subset. Sorting the array (and processing from largest to smallest) is a key optimization. It helps in two ways: first, it prunes the search space faster, and second, it allows us to easily skip duplicate numbers to avoid redundant work. If a path starting with a number x fails, we know that any other path starting with an identical number x will also fail under the same conditions.

1import java.util.Arrays;2 3class Solution {4    public boolean canPartitionKSubsets(int[] nums, int k) {5        int totalSum = 0;6        for (int num : nums) {7            totalSum += num;8        }9        if (k <= 0 || totalSum % k != 0) {10            return false;11        }12        int targetSum = totalSum / k;13        14        Arrays.sort(nums);15        if (nums[nums.length - 1] > targetSum) return false;16 17        return backtrack(nums, k, 0, nums.length - 1, new boolean[nums.length], targetSum);18    }19 20    private boolean backtrack(int[] nums, int k, int currentSum, int startIndex, boolean[] used, int targetSum) {21        if (k == 0) {22            return true;23        }24        if (currentSum == targetSum) {25            // One subset found, search for the next k-1 subsets.26            return backtrack(nums, k - 1, 0, nums.length - 1, used, targetSum);27        }28 29        for (int i = startIndex; i >= 0; i--) {30            if (used[i] || currentSum + nums[i] > targetSum) {31                continue;32            }33            // Optimization: If the previous identical element was not chosen, skip this one too.34            if (i < nums.length - 1 && nums[i] == nums[i+1] && !used[i+1]) {35                continue;36            }37            38            used[i] = true;39            if (backtrack(nums, k, currentSum + nums[i], i - 1, used, targetSum)) {40                return true;41            }42            used[i] = false; // Backtrack43        }44        return false;45    }46}

Complexity

Time

O(N * 2^N). While the exact analysis is complex, this is a common upper bound for this type of problem when memoized. Without memoization, the performance can be worse, but it's generally better than `O(k^N)`. The state can be defined by the mask of used elements (`2^N` possibilities), and for each, we might iterate through `N` numbers.

Space

O(N). The recursion depth can be at most `N`, and we use a boolean array of size `N` to track used elements.

Trade-offs

Pros

More efficient than the first brute-force approach due to better pruning strategies.
The search is more structured, leading to a smaller search space being explored in practice.

Cons

The time complexity is still exponential, making it too slow for larger N.
It recomputes solutions for the same set of remaining numbers, as it lacks memoization.

Given the small constraint on the input size (N <= 16), this problem is a perfect candidate for a solution using dynamic programming with bitmasking. A bitmask, an integer, is used to represent the set of numbers from the input array that have already been placed into subsets. This approach systematically builds up solutions to larger subproblems from smaller ones, storing intermediate results to avoid redundant calculations.

Algorithm

Perform the initial checks for totalSum and targetSum.
Create a DP array, dp, of size 2^N, where N is the number of elements in nums. dp[mask] will store the sum of the last, incomplete subset for the set of numbers represented by mask.
Initialize dp with -1 to signify uncomputed states, and set dp[0] = 0 because an empty set has a sum of 0.
Iterate through all possible bitmasks from 0 to 2^N - 1.
For each mask where dp[mask] is not -1 (i.e., it's a reachable state):
- Iterate through each number nums[i].
- If the i-th bit is not set in mask (meaning nums[i] has not been used yet):
  - Form the nextMask by setting the i-th bit: nextMask = mask | (1 << i).
  - If adding nums[i] to the current subset sum dp[mask] does not exceed targetSum:
    - Update dp[nextMask]. The new sum for the last subset is (dp[mask] + nums[i]). If this sum reaches targetSum, it completes a subset, and the new remainder is 0. This can be concisely written as dp[nextMask] = (dp[mask] + nums[i]) % targetSum.
After filling the DP table, the final answer is dp[(1 << N) - 1] == 0. This checks if all numbers (represented by the mask with all bits set) can be partitioned perfectly with a remainder of 0.

Walkthrough

This method uses a bottom-up DP approach. We define a DP array, dp, of size 2^N. The state dp[mask] represents the sum of the numbers in the last, possibly incomplete, subset, for the combination of numbers represented by the bitmask mask. A value of -1 can indicate an invalid or unreachable state.

The key insight is how to define the state transition. dp[mask] stores (sum of elements in mask) % targetSum. If dp[mask] is 0, it means the elements corresponding to the mask can be perfectly partitioned into some number of subsets of targetSum.

We initialize dp[0] = 0 (an empty set has a sum of 0) and iterate through all masks. For each reachable mask, we try to add a new, unused number nums[i]. If adding nums[i] to the current remainder dp[mask] is less than or equal to targetSum, we update the DP state for the new mask nextMask = mask | (1 << i). The new remainder is (dp[mask] + nums[i]) % targetSum.

The final answer is determined by checking dp[(1 << N) - 1]. If it's 0, it means all numbers can be partitioned into k subsets of equal sum.

1import java.util.Arrays;2 3class Solution {4    public boolean canPartitionKSubsets(int[] nums, int k) {5        int n = nums.length;6        int totalSum = 0;7        for (int num : nums) {8            totalSum += num;9        }10        if (k <= 0 || totalSum % k != 0) {11            return false;12        }13        int targetSum = totalSum / k;14 15        int[] dp = new int[1 << n];16        Arrays.fill(dp, -1);17        dp[0] = 0;18 19        for (int mask = 0; mask < (1 << n); mask++) {20            if (dp[mask] == -1) {21                continue;22            }23            for (int i = 0; i < n; i++) {24                // Check if the i-th element is not in the current subset (mask)25                if ((mask & (1 << i)) == 0) {26                    int nextMask = mask | (1 << i);27                    if (dp[mask] + nums[i] <= targetSum) {28                        dp[nextMask] = (dp[mask] + nums[i]) % targetSum;29                    }30                }31            }32        }33        return dp[(1 << n) - 1] == 0;34    }35}

Complexity

Time

O(N * 2^N). The algorithm involves two nested loops. The outer loop iterates through `2^N` masks, and the inner loop iterates through `N` numbers to decide which one to add next.

Space

O(2^N). The dominant factor is the DP array, which needs to store a value for each of the `2^N` possible bitmasks.

Trade-offs

Pros

This is the most efficient approach for the given constraints.
It guarantees the time complexity by systematically solving each subproblem only once.
It's a standard and powerful technique for problems with small N involving subsets or permutations.

Cons

The space complexity is O(2^N), which is substantial and only feasible because N is small (<= 16).
The logic can be less intuitive to grasp compared to direct backtracking.

Solutions

Solution

1public class Partition_to_K_Equal_Sum_Subsets { class Solution { public boolean canPartitionKSubsets ( int [] nums , int k ) { if ( nums == null || nums . length == 0 || k <= 0 ) { return false ; } int sum = Arrays . stream ( nums ). sum (); if ( sum % k != 0 ) { return false ; } Arrays . sort ( nums ); int target = sum / k ; boolean [] isVisited = new boolean [ nums . length ]; return dfs ( 0 , 0 , k , isVisited , target , nums ); } private boolean dfs ( int startIndex , int currentSum , int k , boolean [] isVisited , int target , int [] nums ) { if ( k == 1 ) return true ; if ( currentSum > target ) return false ; if ( currentSum == target ) { return dfs ( 0 , 0 , k - 1 , isVisited , target , nums ); } for ( int i = startIndex ; i < nums . length ; i ++) { if ( isVisited [ i ]) continue ; isVisited [ i ] = true ; if ( dfs ( i + 1 , currentSum + nums [ i ], k , isVisited , target , nums )) { return true ; } isVisited [ i ] = false ; } return false ; } } // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/ // @todo: investigate more class Solution_dp_Bit_Masking { public boolean canPartitionKSubsets ( int [] nums , int k ) { int N = nums . length ; Arrays . sort ( nums ); int sum = Arrays . stream ( nums ). sum (); int target = sum / k ; if ( sum % k > 0 || nums [ N - 1 ] > target ) return false ; boolean [] dp = new boolean [ 1 << N ]; dp [ 0 ] = true ; int [] total = new int [ 1 << N ]; for ( int state = 0 ; state < ( 1 << N ); state ++) { if (! dp [ state ]) continue ; for ( int i = 0 ; i < N ; i ++) { int future = state | ( 1 << i ); if ( state != future && ! dp [ future ]) { if ( nums [ i ] <= target - ( total [ state ] % target )) { dp [ future ] = true ; total [ future ] = total [ state ] + nums [ i ]; } else { break ; } } } } return dp [( 1 << N ) - 1 ]; } } // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/ // @todo: investigate more class Solution222 { public boolean canPartitionKSubsets ( int [] nums , int k ) { if ( nums == null || nums . length == 0 || k <= 0 ) { return false ; } int sum = Arrays . stream ( nums ). sum (); if ( sum % k > 0 ) { // divident is not int, not possible to achieve return false ; } int target = sum / k ; Arrays . sort ( nums ); int row = nums . length - 1 ; if ( nums [ row ] > target ) return false ; // optimize, early stop while ( row >= 0 && nums [ row ] == target ) { row --; k --; } return dfs ( new int [ k ], row , nums , target ); } public boolean dfs ( int [] groups , int row , int [] nums , int target ) { if ( row < 0 ) { return true ; } int v = nums [ row --]; for ( int i = 0 ; i < groups . length ; i ++) { if ( groups [ i ] + v <= target ) { // try to put every element to each of k groups, for an exhuast search groups [ i ] += v ; if ( dfs ( groups , row , nums , target )) return true ; groups [ i ] -= v ; } if ( groups [ i ] == 0 ) { break ; // all the 0 values of each group occur at the end of the array groups } } return false ; } } } ////// class Solution { public boolean canPartitionKSubsets ( int [] nums , int k ) { int sum = 0 ; for ( int num : nums ) sum += num ; if ( sum % k != 0 ) return false ; int subsum = sum / k ; Arrays . sort ( nums ); int length = nums . length ; if ( nums [ length - 1 ] > subsum ) return false ; boolean [] used = new boolean [ length ]; return backtrack ( nums , k , subsum , 0 , 0 , used ); } private boolean backtrack ( int [] nums , int k , int subsum , int cur , int start , boolean [] used ) { if ( k == 0 ) return true ; if ( cur == subsum ) return backtrack ( nums , k - 1 , subsum , 0 , 0 , used ); int length = nums . length ; for ( int i = start ; i < length ; i ++) { if (! used [ i ] && nums [ i ] + cur <= subsum ) { used [ i ] = true ; if ( backtrack ( nums , k , subsum , nums [ i ] + cur , i + 1 , used )) return true ; used [ i ] = false ; } } return false ; } } ////// class Solution { private int [] nums ; private int [] cur ; private int s ; public boolean canPartitionKSubsets ( int [] nums , int k ) { for ( int v : nums ) { s += v ; } if ( s % k != 0 ) { return false ; } s /= k ; cur = new int [ k ]; Arrays . sort ( nums ); this . nums = nums ; return dfs ( nums . length - 1 ); } private boolean dfs ( int i ) { if ( i < 0 ) { return true ; } for ( int j = 0 ; j < cur . length ; ++ j ) { if ( j > 0 && cur [ j ] == cur [ j - 1 ]) { continue ; } cur [ j ] += nums [ i ]; if ( cur [ j ] <= s && dfs ( i - 1 )) { return true ; } cur [ j ] -= nums [ i ]; } return false ; } }

1''' eg: [1,2,3,4], k=2 s = 5 for its first few recusions, cur[0] is [1,2] when i is at val 3, 1+2+3=6 > s=5, then it will not go further dfs() and i will not +1 anymore so the case of returning False and trimming dfs tree ''' class Solution : def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : def dfs ( i ): if i == len ( nums ): return True for j in range ( k ): # for every bucket # if j => not 0 if j and cur [ j ] == cur [ j - 1 ]: # goal is k blocks all the same, so j must be same as j-1 continue cur [ j ] += nums [ i ] # for nums[i] to try every possible k partition # cannot be 'cur[j] == s', it will not enter follwing dfs() recursion if cur [ j ] <= s and dfs ( i + 1 ): return True cur [ j ] -= nums [ i ] # restore return False s , mod = divmod ( sum ( nums ), k ) if mod : return False cur = [ 0 ] * k nums . sort ( reverse = True ) # if reverse=False, or just no sort, then both will have error 'Time Limit Exceeded' # because, it's like the learning rate of ML-model training, # we want the initial step to be larger to reduce search times, # larger num will fail faster, # while smaller num will continue search on more recursions before failing return dfs ( 0 ) ''' dynamic programming (DP) with bitmasking It iterates through all possible bitmasks and updates the DP array dp based on the conditions of forming subsets with equal sums. It also keeps track of the current subset sum in the subset_sum array. Finally, it checks if the last element in the DP array is True, indicating that it's possible to partition the array into k equal sum subsets. ''' class Solution : # dp version, OJ passed def canPartitionKSubsets ( self , nums , k ): total_sum = sum ( nums ) target_sum = total_sum // k if total_sum % k != 0 or max ( nums ) > target_sum : return False n = len ( nums ) dp = [ False ] * ( 1 << n ) dp [ 0 ] = True subset_sum = [ 0 ] * ( 1 << n ) for mask in range ( 1 << n ): if not dp [ mask ]: continue for i in range ( n ): next_mask = mask | ( 1 << i ) if mask & ( 1 << i ) == 0 and subset_sum [ mask ] % target_sum + nums [ i ] <= target_sum : dp [ next_mask ] = True subset_sum [ next_mask ] = subset_sum [ mask ] + nums [ i ] return dp [( 1 << n ) - 1 ] class Solution : def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : @ cache def dfs ( state , t ): if state == mask : return True for i , v in enumerate ( nums ): if ( state >> i ) & 1 : continue if t + v > s : break if dfs ( state | 1 << i , ( t + v ) % s ): return True return False s , mod = divmod ( sum ( nums ), k ) if mod : return False nums . sort () mask = ( 1 << len ( nums )) - 1 return dfs ( 0 , 0 ) ############# class Solution : # over time limit, no sorting def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : if nums is None or len ( nums ) == 0 or k <= 0 : return False total_sum = sum ( nums ) if total_sum % k != 0 : return False target = total_sum // k nums . sort () is_visited = [ False ] * len ( nums ) return self . dfs ( 0 , 0 , k , is_visited , target , nums ) def dfs ( self , start_index : int , current_sum : int , k : int , is_visited : List [ bool ], target : int , nums : List [ int ]) -> bool : if k == 1 : return True if current_sum > target : return False if current_sum == target : return self . dfs ( 0 , 0 , k - 1 , is_visited , target , nums ) for i in range ( start_index , len ( nums )): if is_visited [ i ]: continue is_visited [ i ] = True if self . dfs ( i + 1 , current_sum + nums [ i ], k , is_visited , target , nums ): return True is_visited [ i ] = False return False ############ class Solution : def canPartitionKSubsets ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: bool """ if not nums or len ( nums ) < k : return False _sum = sum ( nums ) div , mod = divmod ( _sum , k ) if _sum % k or max ( nums ) > _sum / k : return False nums . sort ( reverse = True ) target = [ div ] * k return self . dfs ( nums , k , 0 , target ) def dfs ( self , nums , k , index , target ): if index == len ( nums ): return True num = nums [ index ] for i in range ( k ): if target [ i ] >= num : target [ i ] -= num if self . dfs ( nums , k , index + 1 , target ): return True target [ i ] += num return False

1// OJ: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ // Time: O(K^N) // Space: O(N * SUM(A) / K) class Solution { public: bool canPartitionKSubsets ( vector < int >& A , int k ) { int sum = accumulate ( begin ( A ), end ( A ), 0 ); if ( sum % k ) return false ; sum /= k ; vector < int > v ( k ); sort ( begin ( A ), end ( A ), greater <> ()); // Try the rocks earlier than sands function < bool ( int ) > dfs = [ & ]( int i ) { if ( i == A . size ()) return true ; for ( int j = 0 ; j < k ; ++ j ) { if ( v [ j ] + A [ i ] > sum ) continue ; v [ j ] += A [ i ]; if ( dfs ( i + 1 )) return true ; v [ j ] -= A [ i ]; if ( v [ j ] == 0 ) break ; // don't try empty buckets multiple times. } return false ; }; return dfs ( 0 ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Partition_to_K_Equal_Sum_Subsets { class Solution { public boolean canPartitionKSubsets ( int [] nums , int k ) { if ( nums == null || nums . length == 0 || k <= 0 ) { return false ; } int sum = Arrays . stream ( nums ). sum (); if ( sum % k != 0 ) { return false ; } Arrays . sort ( nums ); int target = sum / k ; boolean [] isVisited = new boolean [ nums . length ]; return dfs ( 0 , 0 , k , isVisited , target , nums ); } private boolean dfs ( int startIndex , int currentSum , int k , boolean [] isVisited , int target , int [] nums ) { if ( k == 1 ) return true ; if ( currentSum > target ) return false ; if ( currentSum == target ) { return dfs ( 0 , 0 , k - 1 , isVisited , target , nums ); } for ( int i = startIndex ; i < nums . length ; i ++) { if ( isVisited [ i ]) continue ; isVisited [ i ] = true ; if ( dfs ( i + 1 , currentSum + nums [ i ], k , isVisited , target , nums )) { return true ; } isVisited [ i ] = false ; } return false ; } } // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/ // @todo: investigate more class Solution_dp_Bit_Masking { public boolean canPartitionKSubsets ( int [] nums , int k ) { int N = nums . length ; Arrays . sort ( nums ); int sum = Arrays . stream ( nums ). sum (); int target = sum / k ; if ( sum % k > 0 || nums [ N - 1 ] > target ) return false ; boolean [] dp = new boolean [ 1 << N ]; dp [ 0 ] = true ; int [] total = new int [ 1 << N ]; for ( int state = 0 ; state < ( 1 << N ); state ++) { if (! dp [ state ]) continue ; for ( int i = 0 ; i < N ; i ++) { int future = state | ( 1 << i ); if ( state != future && ! dp [ future ]) { if ( nums [ i ] <= target - ( total [ state ] % target )) { dp [ future ] = true ; total [ future ] = total [ state ] + nums [ i ]; } else { break ; } } } } return dp [( 1 << N ) - 1 ]; } } // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/ // @todo: investigate more class Solution222 { public boolean canPartitionKSubsets ( int [] nums , int k ) { if ( nums == null || nums . length == 0 || k <= 0 ) { return false ; } int sum = Arrays . stream ( nums ). sum (); if ( sum % k > 0 ) { // divident is not int, not possible to achieve return false ; } int target = sum / k ; Arrays . sort ( nums ); int row = nums . length - 1 ; if ( nums [ row ] > target ) return false ; // optimize, early stop while ( row >= 0 && nums [ row ] == target ) { row --; k --; } return dfs ( new int [ k ], row , nums , target ); } public boolean dfs ( int [] groups , int row , int [] nums , int target ) { if ( row < 0 ) { return true ; } int v = nums [ row --]; for ( int i = 0 ; i < groups . length ; i ++) { if ( groups [ i ] + v <= target ) { // try to put every element to each of k groups, for an exhuast search groups [ i ] += v ; if ( dfs ( groups , row , nums , target )) return true ; groups [ i ] -= v ; } if ( groups [ i ] == 0 ) { break ; // all the 0 values of each group occur at the end of the array groups } } return false ; } } } ////// class Solution { public boolean canPartitionKSubsets ( int [] nums , int k ) { int sum = 0 ; for ( int num : nums ) sum += num ; if ( sum % k != 0 ) return false ; int subsum = sum / k ; Arrays . sort ( nums ); int length = nums . length ; if ( nums [ length - 1 ] > subsum ) return false ; boolean [] used = new boolean [ length ]; return backtrack ( nums , k , subsum , 0 , 0 , used ); } private boolean backtrack ( int [] nums , int k , int subsum , int cur , int start , boolean [] used ) { if ( k == 0 ) return true ; if ( cur == subsum ) return backtrack ( nums , k - 1 , subsum , 0 , 0 , used ); int length = nums . length ; for ( int i = start ; i < length ; i ++) { if (! used [ i ] && nums [ i ] + cur <= subsum ) { used [ i ] = true ; if ( backtrack ( nums , k , subsum , nums [ i ] + cur , i + 1 , used )) return true ; used [ i ] = false ; } } return false ; } } ////// class Solution { private int [] nums ; private int [] cur ; private int s ; public boolean canPartitionKSubsets ( int [] nums , int k ) { for ( int v : nums ) { s += v ; } if ( s % k != 0 ) { return false ; } s /= k ; cur = new int [ k ]; Arrays . sort ( nums ); this . nums = nums ; return dfs ( nums . length - 1 ); } private boolean dfs ( int i ) { if ( i < 0 ) { return true ; } for ( int j = 0 ; j < cur . length ; ++ j ) { if ( j > 0 && cur [ j ] == cur [ j - 1 ]) { continue ; } cur [ j ] += nums [ i ]; if ( cur [ j ] <= s && dfs ( i - 1 )) { return true ; } cur [ j ] -= nums [ i ]; } return false ; } }

1''' eg: [1,2,3,4], k=2 s = 5 for its first few recusions, cur[0] is [1,2] when i is at val 3, 1+2+3=6 > s=5, then it will not go further dfs() and i will not +1 anymore so the case of returning False and trimming dfs tree ''' class Solution : def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : def dfs ( i ): if i == len ( nums ): return True for j in range ( k ): # for every bucket # if j => not 0 if j and cur [ j ] == cur [ j - 1 ]: # goal is k blocks all the same, so j must be same as j-1 continue cur [ j ] += nums [ i ] # for nums[i] to try every possible k partition # cannot be 'cur[j] == s', it will not enter follwing dfs() recursion if cur [ j ] <= s and dfs ( i + 1 ): return True cur [ j ] -= nums [ i ] # restore return False s , mod = divmod ( sum ( nums ), k ) if mod : return False cur = [ 0 ] * k nums . sort ( reverse = True ) # if reverse=False, or just no sort, then both will have error 'Time Limit Exceeded' # because, it's like the learning rate of ML-model training, # we want the initial step to be larger to reduce search times, # larger num will fail faster, # while smaller num will continue search on more recursions before failing return dfs ( 0 ) ''' dynamic programming (DP) with bitmasking It iterates through all possible bitmasks and updates the DP array dp based on the conditions of forming subsets with equal sums. It also keeps track of the current subset sum in the subset_sum array. Finally, it checks if the last element in the DP array is True, indicating that it's possible to partition the array into k equal sum subsets. ''' class Solution : # dp version, OJ passed def canPartitionKSubsets ( self , nums , k ): total_sum = sum ( nums ) target_sum = total_sum // k if total_sum % k != 0 or max ( nums ) > target_sum : return False n = len ( nums ) dp = [ False ] * ( 1 << n ) dp [ 0 ] = True subset_sum = [ 0 ] * ( 1 << n ) for mask in range ( 1 << n ): if not dp [ mask ]: continue for i in range ( n ): next_mask = mask | ( 1 << i ) if mask & ( 1 << i ) == 0 and subset_sum [ mask ] % target_sum + nums [ i ] <= target_sum : dp [ next_mask ] = True subset_sum [ next_mask ] = subset_sum [ mask ] + nums [ i ] return dp [( 1 << n ) - 1 ] class Solution : def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : @ cache def dfs ( state , t ): if state == mask : return True for i , v in enumerate ( nums ): if ( state >> i ) & 1 : continue if t + v > s : break if dfs ( state | 1 << i , ( t + v ) % s ): return True return False s , mod = divmod ( sum ( nums ), k ) if mod : return False nums . sort () mask = ( 1 << len ( nums )) - 1 return dfs ( 0 , 0 ) ############# class Solution : # over time limit, no sorting def canPartitionKSubsets ( self , nums : List [ int ], k : int ) -> bool : if nums is None or len ( nums ) == 0 or k <= 0 : return False total_sum = sum ( nums ) if total_sum % k != 0 : return False target = total_sum // k nums . sort () is_visited = [ False ] * len ( nums ) return self . dfs ( 0 , 0 , k , is_visited , target , nums ) def dfs ( self , start_index : int , current_sum : int , k : int , is_visited : List [ bool ], target : int , nums : List [ int ]) -> bool : if k == 1 : return True if current_sum > target : return False if current_sum == target : return self . dfs ( 0 , 0 , k - 1 , is_visited , target , nums ) for i in range ( start_index , len ( nums )): if is_visited [ i ]: continue is_visited [ i ] = True if self . dfs ( i + 1 , current_sum + nums [ i ], k , is_visited , target , nums ): return True is_visited [ i ] = False return False ############ class Solution : def canPartitionKSubsets ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: bool """ if not nums or len ( nums ) < k : return False _sum = sum ( nums ) div , mod = divmod ( _sum , k ) if _sum % k or max ( nums ) > _sum / k : return False nums . sort ( reverse = True ) target = [ div ] * k return self . dfs ( nums , k , 0 , target ) def dfs ( self , nums , k , index , target ): if index == len ( nums ): return True num = nums [ index ] for i in range ( k ): if target [ i ] >= num : target [ i ] -= num if self . dfs ( nums , k , index + 1 , target ): return True target [ i ] += num return False

1// OJ: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ // Time: O(K^N) // Space: O(N * SUM(A) / K) class Solution { public: bool canPartitionKSubsets ( vector < int >& A , int k ) { int sum = accumulate ( begin ( A ), end ( A ), 0 ); if ( sum % k ) return false ; sum /= k ; vector < int > v ( k ); sort ( begin ( A ), end ( A ), greater <> ()); // Try the rocks earlier than sands function < bool ( int ) > dfs = [ & ]( int i ) { if ( i == A . size ()) return true ; for ( int j = 0 ; j < k ; ++ j ) { if ( v [ j ] + A [ i ] > sum ) continue ; v [ j ] += A [ i ]; if ( dfs ( i + 1 )) return true ; v [ j ] -= A [ i ]; if ( v [ j ] == 0 ) break ; // don't try empty buckets multiple times. } return false ; }; return dfs ( 0 ); } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.