1982. Find Array Given Subset Sums

[zeikar]

Problem link

https://leetcode.com/problems/find-array-given-subset-sums/

Problem Summary

각 부분집합의 합으로 이루어진 배열이 주어질 때 원래의 배열을 찾는 문제.

Solution

어려운 문제.
답이 안 떠올라서 코드도 깔끔하고 설명도 괜찮은 디스커션을 참고했다.

https://leetcode.com/problems/find-array-given-subset-sums/discuss/1431457/Easy-Explanation-for-Noobs-%2B-Python-code-with-comments

아이디어는 다음과 같다.
집합이 있을 때 여기에서 하나의 원소를 골라 이 원소를 포함하거나(including), 포함하지 않는(excluding) 멱집합을 만들 수 있다.
예를 들면 {x, y, z}이면 excluding={ {}, {y}, {z}, {y, z}}, including={ {x}, {x, y}, {x, z}, {x, y, z} 인데 excluding을 잘 보면 x가 빠진 {y, z}의 멱집합이 된다.
이런 식으로 원소를 하나씩 빼가면서 정답을 구할 수 있다.

문제는 x 라는 특정 원소를 어떻게 고를 수 있는가인데, 합의 최대에서 두번째 최대를 빼주면 된다.
만약 x가 양수이면 x + y + z > y + z가 되고 합의 최대에서 두번째 최대를 빼주면 된다.
만약 음수인 경우는 x + y + z < y + z 가 되고 이때는 합의 최대에서 두번째 최대를 뺀 값의 마이너스가 x가 된다.

예시로 {1, 2} 집합에서 3 - 2 = 1 이 되고
{-1, 2} 에서는 2 - 1 = 1, 1*-1 == -1 이 된다.

좀 복잡하긴 한데 코드가 의외로 간단하다.

num 으로는 현재의 최대 합과 두번째 최대합을 뺀 값을 세팅하고 sums 를 돌면서 num이 들어가 있거나 안 들어가 있는 배열을 각각 만들어준다.
마지막 if문은 0 체크인데 0은 공집합의 합이므로 excluding에 무조건 들어가 있어야 한다. excluding에 없는 경우는 음수인데 -1 곱한 num을 넣어준다.

Source Code

from collections import Counter
from typing import List


class Solution:
    def recoverArray(self, n: int, sums: List[int]) -> List[int]:
        result = []
        sums.sort()

        while len(sums) > 1:
            num = sums[-1] - sums[-2]
            count_map = Counter(sums)  # Get count of each element
            excluding = []  # Subset sums that do NOT contain num
            including = []  # Subset sums that contain num

            for x in sums:
                if count_map.get(x) > 0:
                    excluding.append(x)
                    including.append(x + num)
                    count_map[x] -= 1
                    count_map[x + num] -= 1

            # Check validity of excluding set
            if 0 in excluding:
                sums = excluding
                result.append(num)
            else:
                sums = including
                result.append(-1 * num)

        return result