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.