[LeetCode] 416. Partition Equal Subset Sum

처음으로 릿코드 문제를 풀어보았다.

어떤 정수 배열이 주어졌을 때, 이 배열을 '합이 동일한 2개의 부분 집합으로 나눌 수 있는지' 를 판단하는 문제였다.

 

dp를 이용해 풀었다. 아래 알고리즘은 직접 손으로 따라가며 풀면 금방 이해할 수 있을만한 코드이다.

 

TIP! 배열의 합이 22일 때, 배열에 속한 몇가지의 수를 선택해 배열의 합의 절반인 11을 만들 수 있으면 자연스레 선택받지 못한 나머지 수들의 합도 11이 된다. (배열의 합이 짝수인 경우만 2개의 부분 집합으로 나눌 수 있기 때문!)

 

혹시 이런 문제가 백준에도 있다면 댓글 남겨주세요,,

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)

        if total % 2 != 0: return False
        
        total //= 2

        dp = [0] * 20001
        dp[0] = 1
        
        for num in nums:
            idx = total
            while idx-num >= 0 :
                if dp[idx] or dp[idx-num]:
                    dp[idx] = 1
                idx -= 1

            if dp[total]: return True

        return False