698. Partition to K Equal Sum Subsets

Option 1 (Preferred)

option 1 is consistent with how to solve other similar problems

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        list_sum = sum(nums)
        if list_sum % k != 0:
            return False
                
        target_sum = list_sum // k
        nums.sort(reverse = True) 
        sub_sums = [0] * k
        
        def helper(cur_idx):
            if cur_idx == n:
                return True
                    
            seen = set()
            for i in range(k):
                if sub_sums[i] + nums[cur_idx] <= target_sum:
                    if sub_sums[i] not in seen:
                        seen.add(sub_sums[i])
                        sub_sums[i] += nums[cur_idx]
                        if helper(cur_idx+1):
                            return True
                        sub_sums[i] -= nums[cur_idx]

            return False
                    
        return helper(0)

Option 2

using start_idx to avoid processing a number again in the same subset
using visited to avoid processing a number that has been included into another subset

a rough upper bound of time complexity: it takes O(2^n) time complexity to build all 2^n potential first subsets, and it will build k levels in total so total time complexity is O(2^kn)

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        list_sum = sum(nums)
        if list_sum % k != 0:
            return False
                
        target_sum = list_sum // k
        nums.sort() 
        visited = [False] * n
        for i in range(n-1, -1, -1):
            if nums[i] > target_sum:
                return False
            if nums[i] == target_sum:
                visited[i] = True
                k -= 1
            if nums[i] < target_sum:
                break
        
        def helper(start_idx, visited, subset_sum, count):
            if count == 0:
                return True
                    
            for i in range(start_idx, len(nums)):
                if not visited[i]:
                    visited[i] = True
                    if subset_sum + nums[i] < target_sum and helper(i+1, visited, subset_sum + nums[i], count):
                        return True
                    elif subset_sum + nums[i] == target_sum and helper(0, visited, 0, count - 1):
                        return True
                    visited[i] = False
                    
            return False
                    
        return helper(0, visited, 0, k)

698. Partition to K Equal Sum Subsets - cocoder39/coco39_LC GitHub Wiki