<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:
        nums.sort(reverse = True)
        target = sum(nums) // k
        m = {}
        def f(v, curSum, count):
            if v in m:
                return m[v]
            res = False
            if count == k:
                res = True
            elif curSum > target:
                res = False
            elif curSum == target:
                res = f(v, 0, count + 1)
            else:
                for i, n in enumerate(nums):
                    if v & (1 << i) == 0:
                        v ^= 1 << i
                        if f(v, curSum + n, count):
                            res = True
                            break
                        v ^= 1 << i
            m[v] = res
            return res
        return False if sum(nums) % k else f(0, 0, 0)

        # nums.sort(reverse = True)
        # target = sum(nums) // k
        # v = ['0'] * len(nums)
        # m = {}
        # def f(i, curSum, count):
        #     key = ''.join(v)
        #     if key in m:
        #         return m[key]
        #     res = False
        #     if count == k:
        #         res = True
        #     elif curSum > target:
        #         res = False
        #     elif curSum == target:
        #         res = f(0, 0, count + 1)
        #     else:
        #         for j in range(i, len(nums)):
        #             if v[j] == '0':
        #                 v[j] = '1'
        #                 if f(j, curSum + nums[j], count):
        #                     res = True
        #                     break
        #                 v[j] = '0'
        #     m[key] = res
        #     return res
        # return False if sum(nums) % k else f(0, 0, 0)

58160