<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>

#input: nums = list of ints representing nums to make subset from
#k = the num of subsets to make
#output: true if nums can be split into k subsets of equal sum

#can only be done if sum(nums) % k == 0 
#Ex: [1, 2, 4, 3] k = 2 (4, 1), (3, 2): true
#Ex: [3, 4, 4, 1] k = 3: false
#Ex: [5, 4, 4] k = 2: false

#can try testing all comb of subsets
#can be done through backtracking

#recursive backtrack function:
#parameters: nums, k, visited, remaingingsubsetSum
#return true when len(vistied) == len(nums) and remainingSubsetSum == 0: all nums are included in a subset
#elif remaining subsetSum == 0 then call backtrack again with idx = 0 and set remainingSubsetSum to sum(nums)/k to find next subset

#break from backtracking and return when we reach a reaminingSubsetSum < 0
#for i in range(idx, n)
#include i in subset if not included in visited
#add i to visited
#call backtrack with remainingSubsetSum - nums[i]
#remove i from visited

#Ex: [1, 2, 4, 3] k = 2 (4, 1), (3, 2): true
class Solution:

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        if sum(nums) % k != 0:
            return False
        partSum = sum(nums) / k
        n = len(nums)
        endMask = (1 << n) - 1
        memo = {}

        def processNum(currK, mask, curr):
            if currK == k-1:
                return True
            elif mask in memo:
                return memo[mask]

            if curr > partSum:
                return False
            elif curr == partSum:
                currK += 1
                curr = 0

            possible = False

            for i in range(n):
                if (mask & (1 << i)) == 0:
                    if processNum(currK, mask | (1 << i), curr + nums[i]):
                        possible = True

            memo[mask] = possible
            return memo[mask]

        return processNum(0, 0, 0)
50915