<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <code>true</code> if it is possible to divide this array into <code>k</code> non-empty subsets whose sums are all equal.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,3,2,3,5,2,1], k = 4
<strong>Output:</strong> true
<strong>Explanation:</strong> It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], k = 3
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 16</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
	<li>The frequency of each element is in the range <code>[1, 4]</code>.</li>
</ul>

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total, n = sum(nums), len(nums)
        
        # Early exit if the sum isn't divisible by k
        if total % k != 0:
            return False
        
        partsum = total // k
        nums.sort(reverse=True)
        
        # Early exit if any number is greater than the target subset sum
        if nums[0] > partsum:
            return False
        
        visited = [False] * n
        memo = {}
        
        # Helper function for DFS with memoization
        def dfs(kleft, cursum, start):
            # If all k subsets are successfully formed
            if kleft == 0:
                return True
            
            # If the current subset has reached the target sum, start a new subset
            if cursum == partsum:
                return dfs(kleft - 1, 0, 0)
            
            # Use a tuple of visited array as a key for memoization
            state = tuple(visited)
            if state in memo:
                return memo[state]
            
            # Explore numbers for the current subset
            for i in range(start, n):
                if not visited[i] and cursum + nums[i] <= partsum:
                    visited[i] = True
                    if dfs(kleft, cursum + nums[i], i + 1):
                        memo[state] = True
                        return True
                    visited[i] = False

                    # Prune by skipping duplicates
                    if cursum == 0:
                        break
            
            memo[state] = False
            return False
        
        # Start DFS with k subsets, an empty current sum, and the first index
        return dfs(k, 0, 0)

19520