Problem: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] nums[b] nums[c] nums[d] == target

My code is returning duplicates , even I am skipping them . (when I run on my machine it skips the duplicate case) Array [-5,5,4,-3,0,0,4,-2] Target 4

Output
[[-5,5,4,0],[-5,5,0,4],[5,4,-3,-2],[5,-3,4,-2]]
Expected
[[-5,0,4,5],[-3,-2,4,5]]

// solution

class Solution {
    public:
        vector < vector < int >> fourSum(vector < int > & nums, int target) {
            vector < vector < int > > ans;
            int n = nums.size();
            if (n < 4)
                return ans;

            // create a map of two sum

            unordered_map < int, vector < pair < int, int > > > m;
            for (int i = 0; i < n - 1; i  )
                for (int j = i   1; j < n; j  )
                    m[nums[i]   nums[j]].push_back(make_pair(i, j));

            for (int i = 0; i < n - 1; i  ) {
                if (i > 0 and nums[i] == nums[i - 1]) continue;
                for (int j = i   1; j < n; j  ) {
                    if (j > i   1 and nums[j] == nums[j - 1]) continue;
                    int sum = target - nums[i] - nums[j];
                    if (m.find(sum) != m.end()) {
                        for (auto it: m[sum]) {
                            int k = it.first;
                            int l = it.second;
                            if (k > j && l > k) {
                                //Skip invalid cases 

                                if (!ans.empty() and ans.back()[0] == nums[i] and ans.back()[1] == nums[j] and ans.back()[2] == nums[k] and ans.back()[3] == nums[l]) {
                                    continue;
                                }
                                vector < int > temp = {
                                    nums[i],
                                    nums[j],
                                    nums[k],
                                    nums[l]
                                };
                                ans.push_back(temp);

                            }
                        }

                    }
                }
            }
            return ans;
        }

};

CodePudding user response：

If you print out in steps, you can see why and where you get duplicate. For example,

with some 4, you have pairs:

4: [2, 4], [2, 5], [4, 6], [5, 6],

Then, with i=0, j=1, sum = 4, you have duplicate result like this.

i: 0    j: 1    sum: 4
   k: 2 l: 4
   add solution
   k: 2 l: 5
   skip duplicate
   k: 4 l: 6
   add solution
   k: 5 l: 6
   skip duplicate

See, you add to ans result: (0,1,2,4) and (0,1,4,6) which is duplicate. Your condition to check two result is false.

I think you can sort the nums before running your solution. It will ignore duplicate like this.

CodePudding user response：

Start with turning the array into a set. It will remove duplicates.