====== 수집합 ======

===== 풀이 =====
  * 네 수의 합이 0이 되는 조합을 찾는 문제의 변형이다.
  * 이런 문제들은, 모든 네 수의 조합에 대해서 합을 구해보는 O(n^4)방식 대신에, 모든 페어들에 대해서 합을 구해서 저장하고, 그것들을 이용해서 네 수의 합이 특정 값이 되는지 찾는 방식으로 시간 복잡도를 O(n^2)으로 줄일수 있다. 
  * 이 문제에서는 a+b+c=d의 형태이고, 이것을 a+b = d-c로 바꿔쓰면, 모든 페어의 합과 모든 페어의 차를 구해서 중복되는 것이 있는지 찾는 문제로 바뀐다.
  * 물론 단순하게 중복되는 값을 찾기만 하면 되는것은 아니고, 합을 만들때 사용된 두 수와, 차를 만들때 사용된 두 수간에 중복이 없는지를 체크해야 한다. 그것때문에 구현이 좀더 복잡해지긴 한다. 여기서는 합을 키로 갖고, 합을 만들때 사용된 페어들의 리스트를 밸류로 갖는 딕셔너리를 이용해서 구현했다.
  * 총 시간복잡도는 O(n^2)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 4373. 수집합".

- Problem link: https://www.acmicpc.net/problem/4373
- Solution link: http://www.teferi.net/ps/problems/boj/4373
"""

import collections
import itertools
import sys

INF = float('inf')


def main():
    while True:
        n = int(sys.stdin.readline())
        if n == 0:
            break
        S = [int(sys.stdin.readline()) for _ in range(n)]

        answer = -INF
        pairs_by_sum = collections.defaultdict(list)
        for a, b in itertools.combinations(S, 2):
            pairs_by_sum[a + b].append({a, b})
        for d in S:
            if d <= answer:
                continue
            for c in S:
                if c == d:
                    continue
                cd = {c, d}
                ab_list = pairs_by_sum[d - c]
                if any(not (ab & cd) for ab in ab_list):
                    answer = d
                    break
                
        print('no solution' if answer == -INF else answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}