<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 {
public:
   
    map<pair<int , int> , bool> mp ;

    bool func(int sum , int f , int k , int vis , vector<int> &nums)
    {
        if(mp.find({sum , vis}) != mp.end()){
            return mp[{sum , vis}];
        }

        if(sum == k){
            if(vis == f){
                return true ;
            }
            return func(0 , f , k , vis , nums);
        }

        if(sum > k){
            return false ;
        }

        bool flag = false ;

        for(int i = 0 ; i < nums.size() ; i++)
        {
           if(!(vis & (1 << i))){
              int y1 = vis | (1 << i);
              flag = flag | func(sum + nums[i] , f , k , y1 , nums);
           }
        }

        return mp[{sum , vis}] = flag ;

    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        
        int visited = 0 , n = nums.size() ;
        visited = (1 << (n));
        visited -= 1 ;
        int total = 0 ;

        for(auto i:nums){
            total += i ;
        }

        if(total%k){
            return false ;
        }

        k = total/k ;

        return func(0 , visited , k , 0 , nums);

    }
};
78148