[4코3파] #291. Leetcode 416. Partition Equal Subset Sum

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (291일차)
[4코1파] 2023.01.13~ (283일차)
[4코3파] 2023.10.01 ~ (21일차)

Today :

2023.10.21 [291일차]

416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

문제 설명

정수 배열 nums가 주어질 때, 배열을 두 개의 하위 집합으로 분할하여 두 하위 집합의 요소의 합이 같으면 true를 반환하고, false를 반환함 ( => 동일한 합을 가지는 subarray로 분리가능한지에 대한 여부)

문제 풀이 방법

먼저 문제는 주어진 배열을 두 개의 배열로 분리해서 해당 요소들의 합이 같은지 확인하는 문제이므로,
(1) 배열의 합이 짝수여야 가능하다. 배열의 합이 홀수이면 False
(2) sum(nums)/2을 target으로 생각하고, nums 를 탐색하면서 요소들의 합이 target 인지 확인한다.

nums 배열을 탐색하면서 해당 인덱스의 값을 n 이라고 할 때 (1) 해당 인덱스의 n이 dp 배열에 저장되어있는지 (2) 전체에서 n을 뺀 부분합에 저장되어있는지 (3) 전체에서 n을 뺀 부분합이 저장되어 있는지 여부로 True/ False가 갈린다.

brute force로 트리를 타고 내려오면서 부분합 넣으면O(n*sum(nums))가 걸리고, dp로 풀면 o(sum(nums)) 로 풀 수 있다.

내 코드

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        if sum(nums) % 2:
            return False
        
        dp = set()
        dp.add(0)
        target = sum(nums) // 2

        for i in range(len(nums)-1, -1, -1):
            nextDP = set()
            for t in dp:
                # if (t+nums[i]==target):
                #     return True
                nextDP.add(t+nums[i])
                nextDP.add(t)
            dp = nextDP
        return True if target in dp else False

증빙

여담

dp 만 하면 심히 진로에 대해서 고민하게 됨
이게 나랑 맞는건가?