1982. Find Array Given Subset Sums #71
Description
Problem link
https://leetcode.com/problems/find-array-given-subset-sums/
Problem Summary
각 부분집합의 합으로 이루어진 배열이 주어질 때 원래의 배열을 찾는 문제.
Solution
어려운 문제.
답이 안 떠올라서 코드도 깔끔하고 설명도 괜찮은 디스커션을 참고했다.
아이디어는 다음과 같다.
집합이 있을 때 여기에서 하나의 원소를 골라 이 원소를 포함하거나(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