<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:
    # for each element, try to put it into any group
    # TC: 16^16
    # TLE
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)
        n = len(nums)
        if n<k or total%k!=0:
            return False
        
        groups = [0]*k
        target = total//k
        canDo = False

        def search(index):
            nonlocal canDo
            if index == n:
                for i in range(k):
                    if groups[i] != target:
                        return 
                canDo = True
                return
            
            for i in range(k):
                if groups[i]+nums[index] <= target:
                    groups[i] += nums[index]
                    search(index+1)
                    groups[i] -= nums[index]
        
        search(0)
        return canDo

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)
        n = len(nums)
        if n<k or total%k!=0:
            return False
        target = total//k

        canDo = False
        memo = {}

        def search(mask,curVal):
            nonlocal canDo
            if mask == (1<<n)-1:
                # use all value
                return True
            if (mask,curVal) in memo:
                return memo[(mask,curVal)]
            result = False
            for i in range(n):
                if (1<<i)&mask==0 and nums[i]+curVal<=target:
                    result = result or search(mask|(1<<i),(nums[i]+curVal)%target)
            memo[(mask,curVal)] = result
            return memo[(mask,curVal)]
        
        return search(0,0)
        
                
            

       
47293