<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:

    // array of vectors to reach certain sum
    // pairOfSums[n]
    // n : sum of members of each vectors ex) pairOfSums[3] {{2,1,0}, {1,1,1}}
    map<int, vector<pair<int, int>>> pairOfSum;

    // numsInfo is where you find if nums contain enough combination of numbers i guessed
    map<int, int> numsInfo;
    
    int DISTINCT_NUMBERS = 4;

    long int MINIMUM_INT = -294967296;
    long int MAXIMUM_INT = 294967296;
    // dp approach

    bool IsUnique(vector<vector<int>>& answers, vector<int> inAnswer)
    {
        for (int i = 0; i < answers.size(); ++i)
        {
            bool isEqual = true;

            for (int j = 0; j < DISTINCT_NUMBERS; ++j)
            {
                if (answers[i][j] != inAnswer[j])
                {
                    isEqual = false;
                    break;
                }
            }

            if (isEqual)
                return false;
        }

        return true;
    }

    void GetPairOfSums(int target, vector<int> nums, vector<vector<int>>& answers)
    {
        // n^2 time complexity
        for (int i = 0; i < nums.size(); ++i)
        {
            for (int j = i + 1; j < nums.size(); ++j)
            {
                pair<int, int> tempPair = make_pair(nums[i], nums[j]);

                vector<pair<int, int>> matchingPairs = pairOfSum[nums[i] + nums[j]];

                bool isDuplicate = false;
                for (int k = 0; k < matchingPairs.size(); ++k)
                {
                    if (matchingPairs[k].first == tempPair.first &&
                        matchingPairs[k].second == tempPair.second)
                    {
                        isDuplicate = true;
                        break;
                    }
                }

                if(!isDuplicate)
                    pairOfSum[nums[i] + nums[j]].push_back(tempPair);
            }
        }

        for (auto iter : pairOfSum)
        {
            // target - currentSum == another pair exist?
            int currentSum = iter.first;
            
            // index corner case
            if(target < MINIMUM_INT + currentSum ||
            target >MAXIMUM_INT + currentSum)
            {
                continue;
            }

            vector<pair<int, int>> currentPairs = pairOfSum[currentSum];
            vector<pair<int, int>> newPairs = pairOfSum[target - currentSum];

            // if currentPairs and newPairs are all in nums, it is a possible quadruplet
            for (int i = 0; i < currentPairs.size(); ++i)
            {
                int a = currentPairs[i].first;
                int b = currentPairs[i].second;

                for (int j = 0; j < newPairs.size(); ++j)
                {
                    map<int, int> quadraplet;quadraplet[a] = 1;
                    if (quadraplet.find(b) != quadraplet.end())
                    {
                        // if it already exists
                        quadraplet[b]++;
                    }
                    else
                    {
                        // new number found
                        quadraplet[b] = 1;
                    }

                    int c = newPairs[j].first;
                    int d = newPairs[j].second;

                    if (quadraplet.find(c) != quadraplet.end())
                    {
                        // if it already exists
                        quadraplet[c]++;
                    }
                    else
                    {
                        // new number found
                        quadraplet[c] = 1;
                    }

                    if (quadraplet.find(d) != quadraplet.end())
                    {
                        // if it already exists
                        quadraplet[d]++;
                    }
                    else
                    {
                        // new number found
                        quadraplet[d] = 1;
                    }
                    bool isContains = true;
                    for (auto iter : quadraplet)
                    {
                        if (numsInfo[iter.first] < iter.second)
                        {
                            // failed since there are duplicate selected
                            isContains = false;
                            break;
                        }
                    }

                    // add all numbers in pairs to answer
                    vector<int> answer;
                    answer.push_back(a);
                    answer.push_back(b);
                    answer.push_back(c);
                    answer.push_back(d);

                    sort(answer.begin(), answer.end());

                    if (isContains && IsUnique(answers, answer))
                    {
                        answers.push_back(answer);
                    }
                }
            }
        }
    }

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> answers;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); ++i)
        {
            if (numsInfo.find(nums[i]) != numsInfo.end())
            {
                // if it already exists
                numsInfo[nums[i]]++;
            }
            else
            {
                // new number found
                numsInfo[nums[i]] = 1;
            }

        }

        GetPairOfSums(target, nums, answers);

        return answers;
    }
};
71636