<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:
    _TARGET = 0
    
    @cache
    def joinSets(self, sets: Tuple[int], nums: Tuple[int]) -> bool:
        if len(nums) == 0:
            return True
        choice = nums[0]
        exists = False
        for si in range(len(sets)):
            # choice joins s
            newS = sets[si] + choice
            if newS > self._TARGET:
                # invalid
                continue
            newSets = sets[:si] + (newS,) + sets[si+1:]
            exists = exists or self.joinSets(tuple(sorted(newSets)), nums[1:])
        return exists

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        self._TARGET = sum(nums) / k
        results = (0,) * k
        return self.joinSets(results, tuple(sorted(nums, reverse=True)))

21935