# Partition to K Equal Sum Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-to-k-equal-sum-subsets)
Canonical: https://scaleengineer.com/dsa/problems/partition-to-k-equal-sum-subsets
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
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] <= 104`
* The frequency of each element is in the range `[1, 4]`.

# Approaches
## Brute-force Backtracking by Placing Numbers
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.
**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.
**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`.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (k <= 0 || totalSum % k != 0) {
            return false;
        }
        int targetSum = totalSum / k;
        
        // Sort in descending order for optimization
        Arrays.sort(nums);
        for(int i = 0, j = nums.length - 1; i < j; i++, j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        if (nums[0] > targetSum) return false;

        return backtrack(nums, 0, new int[k], targetSum);
    }

    private boolean backtrack(int[] nums, int index, int[] subsetSums, int targetSum) {
        if (index == nums.length) {
            return true;
        }

        int currentNum = nums[index];
        for (int i = 0; i < subsetSums.length; i++) {
            if (subsetSums[i] + currentNum <= targetSum) {
                subsetSums[i] += currentNum;
                if (backtrack(nums, index + 1, subsetSums, targetSum)) {
                    return true;
                }
                subsetSums[i] -= currentNum; // Backtrack
                // Optimization: If this subset was empty, and it failed, 
                // no need to try other empty subsets.
                if (subsetSums[i] == 0) break;
            }
        }
        return false;
    }
}
```
### 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)`.

## Optimized Backtracking by Building Subsets
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (k <= 0 || totalSum % k != 0) {
            return false;
        }
        int targetSum = totalSum / k;
        
        Arrays.sort(nums);
        if (nums[nums.length - 1] > targetSum) return false;

        return backtrack(nums, k, 0, nums.length - 1, new boolean[nums.length], targetSum);
    }

    private boolean backtrack(int[] nums, int k, int currentSum, int startIndex, boolean[] used, int targetSum) {
        if (k == 0) {
            return true;
        }
        if (currentSum == targetSum) {
            // One subset found, search for the next k-1 subsets.
            return backtrack(nums, k - 1, 0, nums.length - 1, used, targetSum);
        }

        for (int i = startIndex; i >= 0; i--) {
            if (used[i] || currentSum + nums[i] > targetSum) {
                continue;
            }
            // Optimization: If the previous identical element was not chosen, skip this one too.
            if (i < nums.length - 1 && nums[i] == nums[i+1] && !used[i+1]) {
                continue;
            }
            
            used[i] = true;
            if (backtrack(nums, k, currentSum + nums[i], i - 1, used, targetSum)) {
                return true;
            }
            used[i] = false; // Backtrack
        }
        return false;
    }
}
```
### 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)`.

## Dynamic Programming with Bitmasking
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int n = nums.length;
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (k <= 0 || totalSum % k != 0) {
            return false;
        }
        int targetSum = totalSum / k;

        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) {
                continue;
            }
            for (int i = 0; i < n; i++) {
                // Check if the i-th element is not in the current subset (mask)
                if ((mask & (1 << i)) == 0) {
                    int nextMask = mask | (1 << i);
                    if (dp[mask] + nums[i] <= targetSum) {
                        dp[nextMask] = (dp[mask] + nums[i]) % targetSum;
                    }
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}
```
### 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.

# Solutions
### Java

```java
public 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 ; } }
```

### Python

```python
''' 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
```

### CPP

```cpp
// 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 ); } };
```