Partition to K Equal Sum Subsets

'''
each bucket size= total_sum/k ie. target
Logic is simple, we will take the elements if cur_sum+nums[i]<=target and pass again for the further elements.if cur_sum==target, means we are done with one bucket so we can iterate again on the nums to fill our another bucket.

Few things to maintain:
1.start with the bigger elements first,it will make it easier because small,small then big might not fit at the end and we will have to reiterate again.
2.To track which of the elemnets are selected already in the previous bucket, we can keep a used_elements array.
3.Once bucket size becomes our target, we need to traverse the whole array again and consider only the unused elements.
4.if cur_sum at the end of the for loop is zero, means even the bigger element couldn't come into the bucket so you can return false.

Time Complexity: 2^n for each element selection and k for each bucket so total time complexity is k*2^n
'''


from typing import List
def dfs(nums, used, start, k, curr_sum, target):
    if k == 1:
        return True

    if curr_sum == target:
        return dfs(nums, used, 0, k - 1, 0, target)

    for i in range(start, len(nums)):
        if used[i]:
            continue

        if curr_sum + nums[i] > target:
            continue

        used[i] = True

        if dfs(nums, used, i + 1, k, curr_sum + nums[i], target):
            return True

        used[i] = False

        # pruning
        if curr_sum == 0:
            return False


    return False


class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)

        if total % k != 0:
            return False

        target = total // k
        nums.sort(reverse=True)  # important
        used = [False] * len(nums)

        return dfs(nums, used, 0, k, 0, target)