[leetcode: python] Partition Equal Subset Sum

Partition Equal Subset Sum

생각한 방식

• [1,5,11,5] 정렬해서 작은 수 + 가장 큰 수로 나누면 될까?

  • 예외 1) [1,2,3,4] 딱 반절로 나눌 수 있을 때
  • 예외 2) [1,2,5,6]
  • 예외 3) [10,5,4,5,4,3,2,1,1,1] = [5,4,5,4] + [10,3,2,1,1,1]
    ⇢ 정렬해서 풀 수 있는 문제가 아니다.

• 구간 합으로 풀어야 하나?

  • 반론) 순서가 상관없어서 이것도 아니다.

풀잇법

예) [1,2,5,6]

sum을 구할 때 어느 숫자는 더해질 수도, 안 더해질 수도 있다.

1이 더해지면 1, 안 더해지면 0이 된다.
이와 같은 경우를 리스트의 모든 숫자에 대해 따져보면 이 리스트로 만들 수 있는 partition subset sum이 나온다. [1,2,5,6]으로 [6,14,8, ..., 6,0]을 만들 수 있다. 가만 보면 숫자 몇 개가 겹친다는 것을 알 수 있다. 하나만 저장하기 위해 set()을 써보자.

코드

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0: return False
        
        sums = set([0]) # 아무것도 더하지 않았을 때
        
        for n in nums: # 숫자 하나를 잡고
            newSums = set()
            
            for s in sums:
                newSums.add(s) # 안 더했을 때 (위 화살표의 오른쪽)
                newSums.add(s+n) # 더했을 때 (위 화살표의 왼쪽)
            sums = newSums
            
            if sum(nums) // 2 in sums: return True
        
        return False

참고 자료

NeetCode's Youtube