[DP: 0 / 1 Knapsack] 416. Partition Equal Subset Sum ★★★

416. Partition Equal Subset Sum

 

잘못된 풀이!!

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # subset 들의 합이 같은게 있으면 return True, 아니면 False
        subsets = []

        def dfsBacktrack(path, start):
            if start == len(path):
                subsets.append(path.copy())

            for i in range(start, len(nums)):
                path.append(nums[i]) # nums[i] 추가
                dfsBacktrack(path, start + 1)
                path.pop() # nums[i] 삭제

        dfsBacktrack([], 0)
        print(subsets)
        subset_sum_list = [sum(subset) for subset in subsets]
        print(subset_sum_list)
        subset_sum_dict = {}
        for sub_total in subset_sum_list:
            if sub_total not in subset_sum_dict:
                subset_sum_dict[sub_total] = 1
            else:
                return True

        return False

 

지금 작성한 코드는 nums 배열의 **모든 부분집합(subset)**을 만들어서,
같은 합을 가진 서로 다른 부분집합이 있는지만 확인하는 방식이에요.

그런데 이건 문제의 조건을 정확히 만족하지 못하는 방식이에요.

---

❌ 문제점 1: "부분집합의 합이 같은 두 집합"이라는 의미 오해

# 현재 코드 의도:
# 같은 합을 가진 subset이 두 개 이상 있으면 return True

하지만 문제의 조건은:

배열을 두 개의 non-overlapping subset으로 나누었을 때,
두 집합의 합이 같은 경우가 존재하느냐예요.

---

❌ 문제점 2: 동일한 원소로 같은 합의 subset 여러 개 나올 수 있음

예를 들어 [1, 1, 1, 1, 2, 2]처럼 같은 값이 반복될 경우,
sum == 3인 subset은 여러 개 나올 수 있지만
이들이 **서로 disjoint(겹치지 않는)**한지 확인은 하지 않음.
즉, 단순히 중복된 합이 있다고 해서 바로 True를 리턴하면 안 돼요.

---

✅ 문제의 정확한 풀이 방향: 0/1 Knapsack 스타일 DP

핵심 아이디어:

• 전체 합을 구해서 totalSum % 2 != 0 이면 바로 False
• 그게 아니라면, 부분집합 중 합이 totalSum // 2인 게 있는지 찾으면 됨!

🎯 문제 목표 다시 정리

nums 배열을 두 개의 subset(부분집합)으로 나누어서, 두 subset의 합이 같게 만들 수 있는지 확인하는 것이 문제입니다.

---

🔍 핵심 아이디어

▶ 전체 합이 홀수면? 절대 나눌 수 없음

왜냐하면, 예를 들어 전체 합이 15라면?

• 두 개의 같은 합으로 나눈다는 건 15 = x + x → x = 7.5인데
• 정수로는 나눌 수 없어요 ❌
• ✅ 그래서 첫 번째 조건:✔️ 전체 합이 홀수이면 절대 불가능하니까 바로 False!
   
  • if totalSum % 2 != 0: return False
• ✅ 두 번째 조건: "전체 합이 짝수면, 그 절반을 만들 수 있는 부분집합이 있으면 True"

---

✅ 정답 코드 (DP 기반)

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)  # 전체 배열의 합 계산

        # ✅ [질문1] 전체 합이 홀수이면 두 부분집합으로 나눌 수 없음
        # 예: total = 15 → 15 / 2 = 7.5 → 정수로 나눌 수 없으므로 False
        if total % 2 != 0:
            return False

        target = total // 2  # 두 부분집합이 가져야 할 합 (절반)

        # ✅ [질문2] dp[t]는 "합이 정확히 t가 되는 부분집합이 존재하는가?"를 의미
        # dp[0] = True인 이유: 아무 것도 선택하지 않는 공집합의 합은 0이므로 항상 True
        dp = [False] * (target + 1)
        dp[0] = True

        # ✅ [질문3] 각 num을 하나씩 사용해서 dp 갱신
        for num in nums:
            # ✅ [질문4] t를 역순으로 순회하는 이유:
            # 현재 num을 중복 사용하지 않기 위해서 → dp[t - num] 값을 참조할 때 오염 방지
            for t in range(target, num - 1, -1):
                # ✅ [질문5] dp[t] = dp[t] or dp[t - num] 의미:
                # "합이 t - num인 경우가 이전에 존재했다면,
                # 지금 num을 추가해서 합이 t도 만들 수 있다"
                #
                # 즉, t를 만들 수 있는 새로운 방법이 생겼는지 확인하는 것
                # dp[t]는 '가능 여부'를 나타내는 불리언 플래그
                dp[t] = dp[t] or dp[t - num]

        # ✅ [질문6] 우리가 찾는 건 "합이 target인 부분집합이 **하나라도** 존재하는가?"
        # dp[target]이 True라면 정답. 여러 개일 필요 없음. 단 하나만 있으면 됨.
        return dp[target]

 

📌 요약된 핵심 포인트

포인트	설명
홀수 합	절대로 두 개의 정수 subset으로 나눌 수 없음
dp[t] 의미	합이 t인 subset이 존재하는가? (True/False)
dp[t] = dp[t] or dp[t - num]	num을 더해서 t를 만들 수 있는지 판단
역순 순회	이전 상태(dp[t - num]) 참조가 오염되지 않게
목표	dp[target] == True인지 여부만 보면 됨 (하나라도 존재하면 OK)

https://youtu.be/IsvocB5BJhw