#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/partition-to-k-equal-sum-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/partition-to-k-equal-sum-implementation

Repovive

Partition to K Equal Sum - Implementation - Complete Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Partition to K Equal Sum - Implementation

Here is the implementation:

function canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return false

    target = total / k
    sort nums descending
    if nums[0] > target:
        return false

    buckets = array of k zeros
    return backtrack(0)

function backtrack(index):
    if index == nums.length:
        return true

    for i from 0 to k - 1:
        if buckets[i] + nums[index] <= target:
            buckets[i] += nums[index]
            if backtrack(index + 1):
                return true
            buckets[i] -= nums[index]

        if buckets[i] == 0:
            break  // Pruning: empty buckets are interchangeable

    return false

Time is $O(k \cdot 2^n)$ worst case, but pruning helps significantly.