class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        num.sort()
        if sum(num[-4:]) < target or sum(num[:4]) > target: # edge case
            return []
        length = len(num)
        if length < 4:
            return []
        solution_set = set()
        for i, a in enumerate(num):
            if a + num[length - 3] + num[length - 2] + num[length - 1] < target:
                continue
            for j in range(i + 1, length):
                if j > i + 1 and num[j] == num[j - 1]:
                    continue
                if a + num[j] + num[length - 2] + num[length - 1] < target:
                    continue
                k, l = j + 1, length - 1
                while k < l:
                    if k > j + 1 and num[k] == num[k - 1]:
                        k += 1
                        continue
                    elif l < length - 1 and num[l] == num[l + 1]:
                        l -= 1
                        continue
                    b, c, d = num[j], num[k], num[l]
                    total = a + b + c + d
                    print a, b, c, d, total
                    if total == target:
                        solution_set.add((a, b, c, d))
                        k += 1
                        l -= 1
                    elif total < target:
                        k += 1
                    else: # total > target
                        l -= 1
        return [list(x) for x in solution_set]

# two sum way

class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        num.sort()
        count = {}
        for a in num:
            count[a] = count.get(a, 0) + 1
        two_sum = {} # O(n^2) space
        length = len(num)
        for i in range(length):
            for j in range(i + 1, length):
                tmp = num[i] + num[j]
                if tmp not in two_sum:
                    two_sum[tmp] = []
                two_sum[tmp].append((num[i], num[j])) # build a list of tuples
        two_sum_list = sorted(two_sum.keys())
        length_2 = len(two_sum_list)
        i, j = 0, length_2 - 1
        output_list = set()
        while i <= j: # equal sign
            a, b = two_sum_list[i], two_sum_list[j]
            four_sum = a + b
            if four_sum == target:
                for tmp_four in [sorted(c + d) for c in two_sum[a] for d in two_sum[b]]: # what about overlapping elements?
                    output_list.add(tuple(tmp_four))
                i += 1
                j -= 1
            elif four_sum < target:
                i += 1
            else: # four_sum > target
                j -= 1
        for tmp_four in list(output_list):
            tmp_count = {}
            for tmp_one in tmp_four:
                tmp_count[tmp_one] = tmp_count.get(tmp_one, 0) + 1
            for tmp_one, cnt in tmp_count.iteritems():
                if cnt > 1 and cnt > count[tmp_one] and tmp_four in output_list:
                    output_list.remove(tmp_four)
        return [list(x) for x in output_list]
        

use two sum