<p>You are given an array <code>nums</code> of positive integers and a <strong>positive</strong> integer <code>k</code>.</p>

<p>A subset of <code>nums</code> is <strong>beautiful</strong> if it does not contain two integers with an absolute difference equal to <code>k</code>.</p>

<p>Return <em>the number of <strong>non-empty beautiful </strong>subsets of the array</em> <code>nums</code>.</p>

<p>A <strong>subset</strong> of <code>nums</code> is an array that can be obtained by deleting some (possibly none) elements from <code>nums</code>. Two subsets are different if and only if the chosen indices to delete are different.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,6], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].
It can be proved that there are only 4 beautiful subsets in the array [2,4,6].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1], k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> The beautiful subset of the array nums is [1].
It can be proved that there is only 1 beautiful subset in the array [1].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 20</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>
</ul>

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
       map<vector<int>,int> cache;

       vector<bool> marked(nums.size(),false);

       return imp(nums,nums.size(),k,0,cache,marked);
    }

    int imp(vector<int>& nums, int n, int k,int start,map<vector<int>,int>& cache,vector<bool>& marked) {
      // auto f=cache.find(nums);
     //  if(f!=cache.end()) return f->second;

       int r=0;

       for(int i=start;i<n;++i) {
        if(marked[i]) continue;

         r++;

         auto m2=marked;
         for(int j=i+1;j<n;++j)
          if(abs(nums[j]-nums[i])==k)
            marked[j]=true;

          r+= imp(nums,n, k,i+1, cache,marked);

          marked = m2;
       }

      // cache[nums]=r;
       return r;
    }
};
197652