<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 {
  int n, subsetSum;
  unordered_map<string, bool> stateIndex;
public:

    bool backtrack(int index, int requiredSubsetSum, int k, vector<int>&nums, vector<bool>& visited, string& currentState){
      
      if(k==1)return true;

      if(stateIndex.find(currentState) != stateIndex.end()){
        return stateIndex[currentState];
      }
      
      if(requiredSubsetSum==0){
        return stateIndex[currentState] = backtrack(0, subsetSum, k-1, nums, visited, currentState);
      }
      
      for(int i=index;i<n;i++){
        if(visited[i])continue;
        if(nums[i]>requiredSubsetSum)break;
        visited[i]=true;
        currentState[i]='1';
        if(backtrack(i+1, requiredSubsetSum-nums[i], k, nums, visited, currentState)){
          return true;
        }
        currentState[i]='0';
        visited[i] = false;
      }
      return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
      int sm = 0;
      n = nums.size();
      for(int i=0;i<n;i++)sm+=nums[i];
      if(sm%k != 0)return false;
      subsetSum = sm/k;

      sort(nums.begin(), nums.end());
      vector<bool> visited(n, false);
      string currentState(n, '0');

      return backtrack(0, subsetSum, k, nums, visited, currentState);
    }
};
19495