leetcode: 18. 4Sum

# Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
# Find all unique quadruplets in the array which gives the sum of target.
#
# Note: The solution set must not contain duplicate quadruplets.
#
# For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
#
# A solution set is:
# [
#   [-1,  0, 0, 1],
#   [-2, -1, 1, 2],
#   [-2,  0, 0, 2]
# ]

# TODO: Cannot ac in python3, but pass in python2


class Solution():
    def fourSum(self, x, target):
        x.sort()
        res = []
        for i in range(len(x) - 3):
            if i == 0 or x[i] != x[i - 1]:
                for j in range(i + 1, len(x) - 2):
                    if j == i + 1 or x[j] != x[j - 1]:
                        mid, right = j + 1, len(x) - 1
                        while mid < right:
                            dis = (x[i] + x[j] + x[mid] + x[right]) - target
                            if dis == 0:
                                res.append([x[i], x[j], x[mid], x[right]])
                                mid, right = mid + 1, right - 1
                                while mid < right and x[mid] == x[mid - 1]:
                                    mid += 1
                                while mid < right and x[right] == x[right + 1]:
                                    right -= 1
                            elif dis < 0:
                                mid += 1
                            else:
                                right -= 1
        return res


if __name__ == '__main__':
    assert Solution().fourSum([1, 0, -1, 0, -2, 2], 0) == [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]