<p>Given an array <code>nums</code> of <code>n</code> integers, return <em>an array of all the <strong>unique</strong> quadruplets</em> <code>[nums[a], nums[b], nums[c], nums[d]]</code> such that:</p>

<ul>
	<li><code>0 &lt;= a, b, c, d&nbsp;&lt; n</code></li>
	<li><code>a</code>, <code>b</code>, <code>c</code>, and <code>d</code> are <strong>distinct</strong>.</li>
	<li><code>nums[a] + nums[b] + nums[c] + nums[d] == target</code></li>
</ul>

<p>You may return the answer in <strong>any order</strong>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,0,-1,0,-2,2], target = 0
<strong>Output:</strong> [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,2,2,2,2], target = 8
<strong>Output:</strong> [[2,2,2,2]]
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= target &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    vector<vector<int>> solutions;
    set<int> seen;
    int bound;
    int size;
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) return {};
        
        sort(nums.begin(),nums.end());
        vector<int> uniqueNums = {nums[0]};
        vector<int> counts = {1};
        for (int i = 1; i < nums.size(); i ++){
            if (nums[i] == uniqueNums.back()) counts.back()++;
            else {
                counts.push_back(1);
                uniqueNums.push_back(nums[i]);
            }
            
        }
        
        int p1 = 0, p2;
        counts[0]--;
        if (counts[0] > 0) p2 = 0;
        else p2 = 1;
        counts[p2]--;
        int p4 = uniqueNums.size()-1, p3;
        counts.back()--;
        if (counts.back() > 0) p3 = p4;
        else p3 = p4-1;
        counts[p3]--;
        bound = target/4;
        long sum =  (long) uniqueNums[p1] + uniqueNums[p2] + uniqueNums[p3] + uniqueNums[p4];
        if (sum > INT_MAX) return solutions;
        size = uniqueNums.size();
        traverse(uniqueNums,counts,p1,p2,p3,p4,sum,target);
        
        return solutions;
    }
    void traverse(vector<int>& nums, vector<int>& counts, int p1, int p2, int p3, int p4, int sum, int& target){    
        if (nums[p1] > bound || nums[p4] < bound) return;
        long hash = size * (size * (size * p4 + p3) + p2) + p1;
        if (seen.find(hash) != seen.end()) return;
        seen.insert(hash);
        if (sum > target){
            if (p3 < p4 && counts[p4-1] > 0) {
              
                    counts[p4-1]--;
                    counts[p4]++;
                    traverse(nums,counts,p1,p2,p3,p4-1,sum - nums[p4] +nums[p4-1],target);
                    counts[p4-1]++;
                    counts[p4]--;
            }
            if (p2 < p3 && counts[p3-1] > 0) {
            
                    counts[p3-1]--;
                    counts[p3]++;
                    traverse(nums,counts,p1,p2,p3-1,p4,sum - nums[p3] + nums[p3-1],target);
                    counts[p3-1]++;
                    counts[p3]--;
            }
            
        }
        else if (sum < target){
            if (p1 < p2 && counts[p1+1] > 0){
              
                    counts[p1+1]--;
                    counts[p1]++;
                    traverse(nums,counts,p1+1,p2,p3,p4,sum - nums[p1] + nums[p1+1],target);
                    counts[p1+1]++;
                    counts[p1]--;
            } 
            if (p2 < p3 && counts[p2+1] > 0) {
                
                    counts[p2+1]--;
                    counts[p2]++;
                    traverse(nums,counts,p1,p2+1,p3,p4,sum - nums[p2] + nums[p2+1],target);
                    counts[p2+1]++;
                    counts[p2]--;
            }
        }
        else{
            solutions.push_back({nums[p1],nums[p2],nums[p3],nums[p4]});
            if (p1 < p2){
                if (!(p1 + 1 == p2 && counts[p2] == 0)){
                    sum += nums[p1+1] - nums[p1];
                    counts[p1+1]--;
                    counts[p1]++;
                    if (p2 < p3 && counts[p3-1] > 0){ 
                    
                            counts[p3-1]--;
                            counts[p3]++;
                            traverse(nums,counts,p1 + 1,p2,p3-1,p4,sum - nums[p3] + nums[p3-1],target);
                            counts[p3-1]++;
                            counts[p3]--;
                    }
                    
                    if (p3 < p4 && counts[p4-1] > 0){
                      
                            counts[p4-1]--;
                            counts[p4]++;
                            traverse(nums,counts,p1+1,p2,p3,p4-1,sum - nums[p4] +nums[p4-1],target);
                            counts[p4-1]++;
                            counts[p4]--;
                    }
                        
                    counts[p1+1]++;
                    counts[p1]--;
                    sum -= nums[p1+1] - nums[p1];
                }
                
            }
            if (p2 < p3 && counts[p2+1] > 0){
                counts[p2+1]--;
                counts[p2]++;
                sum += nums[p2+1] - nums[p2];
                
                if (p3 < p4 && counts[p4-1] > 0) {
                        counts[p4-1]--;
                        counts[p4]++;
                        traverse(nums,counts,p1,p2+1,p3,p4-1,sum - nums[p4] + nums[p4-1],target);
                        counts[p4-1]++;
                        counts[p4]--;
                }
                if (p2 + 1 < p3 && counts[p3-1] > 0) {
                  
                        counts[p3-1]--;
                        counts[p3]++;
                        traverse(nums,counts,p1,p2+1,p3-1,p4,sum - nums[p3] + nums[p3-1],target);
                        counts[p3-1]++;
                        counts[p3]--;
                }
                counts[p2+1]++;
                counts[p2]--;
            }
        }
        
    }
   
};
59881