<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:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
              

              int a = accumulate(nums.begin(),nums.end(),0);   
              int b = a / k ;
              int c = a % k ;  
              if( c != 0) return 0 ;
              cout<<"a="<<a<<endl;
             cout<<"b="<<b<<endl;
              sort(nums.begin(),nums.end());
    
             map< vector<int> ,int>p;
        


        return perm( nums ,b,p); 

    }

   int perm(vector<int> nums ,int& b ,map<vector<int>,int>&p ){

          
        if(nums.size() == 1){
            if(nums[0]==b) return 1;
            else  return 0 ;
               
       }   
       
     if(p.count(nums) > 0 ) return p[nums];

       if(nums[0]>=b){ 
         if(nums[0]==b){  
           nums.erase(nums .begin()) ;
            return  perm(nums ,  b ,p) ;
         }
         else
           p[nums]= 0 ; 
           return 0 ; 
       }

     

       for(int i = 1 ; i < nums.size() ; i++ ){
         int kp = nums[0]+nums[i]; 
            
          if(  kp <= b ) {
      
           vector<int> tp =  nums ;
           tp[0]=kp;
            tp .erase(tp .begin()+i) ;
            if(  perm(tp , b ,p )  ) 
            {  
                p[tp]= 1 ; 
                return 1;
            }
           
          } 
          else {
            p[nums]= 0 ;
            return 0 ;
          }   

       }

             p[nums]=0;
            return 0;
   }



};
73091