알고리즘/LeetCode

[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 tot..