Leetcode Problem 698. Partition to K Equal Sum Subsets
698. Partition to K Equal Sum Subsets
Leetcode Solutions
Backtracking plus Memoization with Bitmasking
Calculate the total sum of the array and check if it is divisible by k. If not, return false as it is not possible to partition the array.
Define a recursive function that takes the current bitmask, the current sum of the subset, the current number of completed subsets, and the index to start from.
If the number of completed subsets is k-1, return true as the remaining elements must form a valid subset.
If the current sum equals the target sum, increment the number of completed subsets and reset the current sum to zero.
Use the bitmask to check for each element if it has been included in a subset. If not, and if adding it to the current sum does not exceed the target sum, include the element by updating the bitmask and the current sum.
Make a recursive call with the updated parameters. If it returns true, memoize the result and return true.
If no valid partition is found, backtrack by resetting the changes to the bitmask and the current sum, and continue with the next element.
Memoize the result for the current bitmask before returning false.
Start the recursion with an initial bitmask of zero, a current sum of zero, the number of completed subsets as zero, and starting index as zero.