Leetcode 698. Partition to K Equal Sum Subsets

Problem

Leetcode 698 - Matchsticks to Square

Example:

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.

Input: nums = [1,2,3,4], k = 3
Output: false

Approach

Similar to matchsticks problem,

We can solve this problem using DFS and sorting. First sort first, then we can use greedy approach and put each side into array as long as the side’s length doesn’t go over the total of nums / k.

Here is the Python code for the solution:

class Solution:
        def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        n = [0] * k
        nums.sort(reverse=True)
        total_length = sum(nums)
        
        if total_length % k != 0:
            return False
        
        length = total_length // k
        
        def dfs(i):
            if i == len(nums):
                return True
            
            for j in range(k):
                if n[j] + nums[i] <= length:
                    n[j] += nums[i]
                    if dfs(i+1):
                        return True
                    n[j] -= nums[i]
                
                if n[j] == 0:
                    break
            
            return False
        
        return dfs(0)
    

Time Complexity and Space Complexity

Time Complexity: $O(4^n)$

Space Complexity: $O(n)$