<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, arr: List[int], k: int) -> bool:
    # If the total sum is not divisible by k, we can't make subsets.
    total_array_sum = sum(arr)
    if total_array_sum % k != 0:
      return False
    target_sum = total_array_sum // k
    if max(arr) > target_sum:
      return False

    # Sort in decreasing order.
    arr.sort(reverse=True)
    dp = {}

    def backtrack(cur_id, cur_setid, cur_sum, mask):
      # We made k - 1 subsets with target sum and the last subset will also have target sum.
      if cur_setid == k - 1:
        return True

      # No need to proceed further.
      if cur_sum > target_sum:
        return False

      # No need to update cache for this condition. Simply return the answer that will never be
      # adopted by its parent caller. E.g., for getting min, return math.inf.
      if cur_id >= len(arr):
        return False

      state = (mask, cur_sum, cur_setid)
      if state in dp:
        return dp[state]

      # When curr sum reaches target then one subset is made.
      # Increment count and reset current sum.
      if cur_sum == target_sum:
        dp[state] = backtrack(0, cur_setid + 1, 0, mask)
        return dp[state]

      # Not take the current index.
      if backtrack(cur_id + 1, cur_setid, cur_sum, mask):
        dp[state] = True
        return True

      if mask & (1 << cur_id) == 0:
        # Include this element in current subset.
        next_mask = (mask | (1 << cur_id))

        # If using current element in this subset leads to make all valid subsets.
        if backtrack(cur_id + 1, cur_setid, cur_sum + arr[cur_id], next_mask):
          dp[state] = True
          return True

      dp[state] = False
      return dp[state]

    return backtrack(0, 0, 0, 0)
23746