<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:
        if sum(nums) % k != 0:
            return False
        target = int(sum(nums)/k)

        '''
        target * k = sum(nums)
        sum(a1) = ... = sum(ak) = target

        '''
        if max(nums) > target:
            return False

        freq = {}
        for num in nums:
            if num not in freq:
                freq[num] = 1
            else:
                freq[num] += 1
        dp = [[] for i in range(target+1)]
        dp[0] = [[]]
        for num in nums:
            v = 1
            for idx in range(target,0,-1):
                toAdd = [num for i in range(v)]
                for times in range(v,0,-1):
                    if idx - num * times >= 0 and len(dp[idx - num * times]) > 0:
                        for lst in dp[idx - num * times]:
                            dp[idx].append(lst + toAdd)
                    toAdd.pop()
        # print(dp[-1])

        def verifyCombine(freq1, freq2):
            for num,v in freq.items():
                x1 = 0
                x2 = 0
                if num in freq1:
                    x1 = freq1[num]
                if num in freq2:
                    x2 = freq2[num]
                if x1 + x2 > freq[num]:
                    return False
            return True

        def combineDicts(freq1, freq2):
            freqcombine = {}
            for num,v in freq1.items():
                freqcombine[num] = v
            for num,v in freq2.items():
                if num in freqcombine:
                    freqcombine[num] += v
                else:
                    freqcombine[num] = v
            return freqcombine

        freqdp = [[] for i in range(k+1)]
        freqdp[0] = [{}]
        # freqoptions = []
        dpoptions = set()
        for lst in dp[-1]:
            dpoptions.add(tuple(sorted(lst)))
        freqoptions = []
        # for lst in dp[-1]:
        for lst in dpoptions:
            curFreq = {}
            for num in lst:
                if num in curFreq:
                    curFreq[num] += 1
                else:
                    curFreq[num] = 1
            freqoptions.append(curFreq)
            
        # for curFreq in freqoptions:
        #     for idx in range(k,0,-1):
        #         if len(freqdp[idx-1]) >= 0:
        #             for entry in freqdp[idx-1]:
        #                 if verifyCombine(entry, curFreq):
        #                     freqdp[idx].append(combineDicts(entry, curFreq))
        for idx in range(1,k+1):
            for curFreq in freqoptions:
                if len(freqdp[idx-1]) >= 0:
                    for entry in freqdp[idx-1]:
                        if verifyCombine(entry, curFreq):
                            freqdp[idx].append(combineDicts(entry, curFreq))
        return len(freqdp[-1]) > 0

24350