Naive Solution: Brute Force

A brute-force approach would involve generating all possible subsets of the input array and checking if we can form k subsets with equal sums. This method is highly inefficient due to the exponential number of possible subsets.

• Time Complexity: O(2^(n*k)), where n is the number of elements in the array.
• Space Complexity: O(n), primarily for recursion stack.

Optimal Solution: Dynamic Programming with Bit Masking

A more efficient approach uses dynamic programming and bit masking to track which elements have been used in subsets. The main idea is as follows:

1. Calculate the Target Sum: Calculate the sum of all elements in nums. If the sum is not divisible by k, we cannot divide the array into k equal sum subsets, so return false.
2. Determine Subset Target Sum: Divide the total sum by k to get the target sum for each subset.
3. DP with Bit Masking: Use a DP array where each index represents a bitmask indicating which elements from nums are already used in subsets. The value at each index is a boolean: true if it's possible to form subsets with the given mask and target sum, false otherwise.

Algorithm

1. Calculate totalSum and check if totalSum % k == 0. If not, return false.
2. Calculate targetSum = totalSum / k.
3. Create a dp array of size 2^n, initialized to false. dp[0] = true because an empty subset is always valid.
4. Iterate through all possible bitmasks from 0 to 2^n - 1:
   • If dp[mask] is true, iterate through each element in nums:
     • If the i-th element is not in the current mask (i.e., (mask & (1 << i)) == 0):
       • Calculate the new mask: newMask = mask | (1 << i).
       • If the sum of the subset represented by newMask does not exceed targetSum, set dp[newMask] = true.
5. After iterating through all masks, dp[(1 << n) - 1] will be true if it's possible to divide the array into k subsets with equal sums. Return this value.

Edge Cases

• If the array is empty or k is non-positive, handle the edge case appropriately. Should return true if the array is empty and k is 1, false otherwise.
• If any element in the array is greater than the target sum, it's impossible to form valid subsets.

Code

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        
        target_sum = total_sum // k
        n = len(nums)
        dp = [False] * (1 << n)
        dp[0] = True

        for mask in range(1 << n):
            if not dp[mask]:
                continue
            for i in range(n):
                if not (mask & (1 << i)):
                    new_mask = mask | (1 << i)
                    subset_sum = 0
                    for j in range(n):
                        if (new_mask & (1 << j)):
                            subset_sum += nums[j]
                    
                    temp_sum = 0
                    temp_mask = new_mask
                    for j in range(n):
                        if (mask & (1 << j)):
                            temp_sum += nums[j]
                    
                    subset_sum_diff = subset_sum - temp_sum
                            
                    if subset_sum_diff <= target_sum:
                       
                        temp_sum_new_mask = 0
                        bin_num = bin(new_mask)[2:].zfill(n)
                        for bit_index in range(len(bin_num)):
                            if bin_num[bit_index] == '1':
                                temp_sum_new_mask += nums[bit_index]
                        
                        if temp_sum_new_mask % target_sum == 0:
                            dp[new_mask] = True
                        elif temp_sum_new_mask < target_sum:
                            dp[new_mask] = True
                        else:
                            dp[new_mask] = False

        return dp[(1 << n) - 1]

• Time Complexity: O(n * 2^n), where n is the number of elements in the array.
• Space Complexity: O(2^n), for the DP array.