LeetCode/Grind169
416. Partition Equal Subset Sum: DP로 꼭 풀어야! ☆☆★★★
hyunkookim
2025. 4. 26. 08:55
416. Partition Equal Subset Sum
Partition Equal Subset Sum 문제는 DP(동적 계획법) 클래식 문제야. ✨
✅ 문제 요약
- nums 배열을 두 부분으로 나누어서
- 각 부분의 합이 같게 만들 수 있는지 True/False로 답하는 문제야.
🧠 핵심 아이디어
- 전체 합(total)을 먼저 구한다.
- total이 홀수면, 두 부분으로 절대 나눌 수 없다 → 바로 False
- total이 짝수면, target = total // 2로 설정한다.
- 그다음, nums 중 일부 원소를 골라서 합이 target이 되는 조합이 있는지 찾는 문제로 바뀐다.
👉 이건 Subset Sum 문제야!
✨ 풀이 전략 (DP)
- dp[i] = sum이 i가 되는 부분집합이 가능한가?
- dp[0] = True (합 0은 아무것도 선택 안 하면 만들 수 있음)
🛠 코드 (Bottom-up DP)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
# 총합이 홀수면 두 개의 같은 합으로 나눌 수 없다
if total % 2 != 0:
return False
target = total // 2 # 두 부분집합이 가져야 할 목표 합
# dp[i] = 합이 i인 부분집합을 만들 수 있는가? (True/False)
dp = [False] * (target + 1)
dp[0] = True # 합이 0은 아무것도 선택하지 않으면 만들 수 있으므로 True
# 모든 숫자들을 하나씩 확인하면서 dp 테이블 업데이트
for num in nums:
# 역순으로 순회 (중복 사용 방지: 현재 num을 여러 번 쓰지 않게)
for i in range(target, num - 1, -1):
# 현재 i를 만들 수 있거나,
# (i - num)을 만들 수 있으면, 거기에 num을 더해서 i를 만들 수 있음
dp[i] = dp[i] or dp[i - num]
# 최종적으로 target 합을 만들 수 있으면 True, 아니면 False
return dp[target]📦 흐름 정리
| 단계 | 설명 |
| total 계산 | 전체 합 구하기 |
| total % 2 확인 | 홀수면 바로 False |
| target 설정 | target = total // 2 |
| dp 테이블 구성 | dp[i]: 합 i를 만들 수 있는가 |
| nums 하나씩 돌며 dp 갱신 | 뒤에서 앞으로 갱신해서 중복 사용 방지 |
| 최종 결과 | dp[target]이 True면 가능 |
🎯 한 문장 요약
"배열을 두 부분으로 나누는 문제는 total이 짝수인지 확인하고,
그 절반을 만드는 subset이 존재하는지 DP로 확인한다."
📢 시간/공간 복잡도
| 시간 | O(n × target) |
| 공간 | O(target) |
- n = 배열 길이
- target = total // 2
🧠 만약, for 를 작->큰 순서로 하면?? 코드도 에러 나긴함.!!
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# sum(더하는 셋) == sum(빼는 셋) 이므로, 토털합은 무조건 짝수
total = sum(nums)
if total % 2 != 0:
return False
# sum(더하는 셋) 또는 sum(빼는 셋)이 total //2 만족하는지..
target = total //2
dp = [False] * (target+1) # dp[타켓]: 타겟 만드는게 가능한지
dp[0] = True # 0 은 아무것도 안하면 만들어짐
for num in nums:
if dp[num] == False:
dp[num] = True
for t in range(num, target+1):
dp[t] = dp[t] or dp[t-num]
return dp[target]
너가 준 두 번째 코드 (for t in range(num, target+1))는 틀렸어. 이유를 설명할게.
네가 수정한 버전 흐름
for num in nums:
if dp[num] == False:
dp[num] = True
for t in range(num, target+1):
dp[t] = dp[t] or dp[t-num]
틀린 이유:
- for t in range(num, target+1) 이렇게 작은 값부터 큰 값 순서로 업데이트하면,
- 현재 num을 여러 번 쓰는 경우가 생긴다.
즉, 하나의 num을 중복 사용하게 되어버려. (❌)
원래 의도는 뭐였냐면
- 각 num은 한 번만 써야 해.
- 즉, num을 넣을지 말지 한 번 결정하고 넘어가야 해.
- 그래서 원래는 for t in range(target, num-1, -1)
→ 큰 값부터 작은 값으로 거꾸로 가야 했던 거야!
거꾸로 가야, 아직 처리 안한 num을 가지고 dp를 업데이트하지 않는다.
쉽게 예시 들어볼게
nums = [1, 5, 11, 5] target = 11
작은-> 큰 순서 방식대로 하면:
- num=1
- dp[1] = True
- dp[2], dp[3], ..., dp[11]까지 전부 1을 가지고 만들 수 있게 업데이트.
- num=5
- dp[5] = True
- dp[6], dp[7], ..., dp[11]을 업데이트.
이때 dp[6] = dp[6] or dp[6-5] = dp[1]이 True니까 dp[6]=True 됨.
- 근데 여기서 6은 1+5 조합이 아니라 5+1을 중복해서 쓴 효과가 나.
- num 하나당 한 번만 써야하는데, dp를 업데이트하면서 1을 두 번 쓰게 되어버림.
정리
| range(target, num-1, -1) (정답) | num 하나만 사용해서 dp 업데이트. |
| range(num, target+1) (틀림) | num을 여러 번 중복해서 쓰는 문제가 생김. |
🔥 요약
- for t in range(target, num-1, -1) (뒤에서 앞으로)
→ num 하나당 딱 한 번만 고려하게 만드는 거야!
✅ 최종 정리
- 원래 정답은:
for num in nums:
for t in range(target, num-1, -1):
dp[t] = dp[t] or dp[t-num]한줄로 정리하면:
👉 "0/1 Knapsack 문제는 항상 뒤에서부터 앞으로 돈다!" 기억하면 돼. (Subset sum = 0/1 knapsack이야.)
✨ DFS + Memoization 풀이
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
# 전체 합이 홀수면 절대 둘로 나눌 수 없음
if total % 2 != 0:
return False
target = total // 2
memo = {}
def dfs(i, curSum):
# 성공 조건: 정확히 target 만들었으면 True
if curSum == target:
return True
# 실패 조건: 합이 target 넘으면 실패
if curSum > target or i == len(nums):
return False
# 메모이제이션 체크
if (i, curSum) in memo:
return memo[(i, curSum)]
# 현재 nums[i]를 선택하는 경우 또는 선택하지 않는 경우
pick = dfs(i + 1, curSum + nums[i])
skip = dfs(i + 1, curSum)
memo[(i, curSum)] = pick or skip
return memo[(i, curSum)]
return dfs(0, 0)
=> 시간 제한에 걸림!!
🧠 흐름 설명
| 단계 | 설명 |
| total 합 구하기 | 전체 합이 홀수면 False |
| target 설정 | total // 2 |
| dfs(i, curSum) | i번째 인덱스에서 현재 합 curSum으로 갈 수 있는지 확인 |
| 성공조건 | curSum == target |
| 실패조건 | curSum > target 또는 배열 끝까지 갔는데 target 못 채움 |
| 재귀 분기 | 현재 숫자를 "선택"하거나 "선택하지 않거나" 둘 다 해봄 |
| memo[(i, curSum)] | (i, curSum) 상태에서의 결과를 저장 |
📦 시간/공간 복잡도
| 시간복잡도 | O(n × target) |
| 공간복잡도 | O(n × target) |
- n = nums 길이
- target = total // 2
- memo 테이블이 (i, curSum) 쌍을 저장하니까 O(n × target)
✅ 완전탐색 대비 엄청 빨라진다.
🎯 한 문장 요약
"DFS로 숫자를 고르거나 건너뛰는 모든 경로를 탐색하고,
(i, curSum) 상태를 memoization으로 저장해 중복 탐색을 막는다."
✨ 정리
| 방법 | 장점 | 단점 |
| DFS+Memoization | 코드 짧고 논리 명확 | 호출 많으면 느림 (TLE 가능성, 시간 제한에 걸림!!) |
| Bottom-Up DP | 한번에 테이블 채워서 중복 없음 | 메모리 적게 쓰고 빠름 |
✅ 그래서 이 문제는 Bottom-Up DP (반복문으로 푸는 방법) 을 쓰는 게 훨씬 안전하고 빠르다.
최종 코드
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 더하기 그룹 - 빼기 그룹 = 0 ==> 총합 이 짝수여야 함
total = sum(nums)
if total % 2 == 1:
return False
target = total //2
# 원소들 더해서 half 되면 true
# dp로
dp = [False] * (target+1)
dp[0] = True # 0 만드는것은 하나도 선택안하면 되니깐
for num in nums:
"""
이 부분 없어도 됨!!
# if num <= target and dp[num] == False:
# dp[num] = True # 왜냐 원래 값이 있으니.
왜냐?
dp[t] = dp[t] or dp[t-num]
이부분 에서, t = num 일때
dp[num] = dp[num] or dp[0] 으로 인해, dp[0] = True 이니,
dp[num] = dp[num] or True
dp[num] = True 로 업데이트 됨!!
"""
for t in range(target, num-1, -1): # 거꾸로..루틴 !!
dp[t] = dp[t] or dp[t-num]
return dp[target]
✅ 1. 이 코드가 하는 일
if num <= target and dp[num] == False:
dp[num] = True→ num이라는 숫자 하나만 선택했을 때 dp[num] = True로 표시하는 거예요.
즉, "num만으로도 target 일부를 만들 수 있다"는 걸 의미합니다.
예를 들어, num=3이면 dp[3]=True로 만든다는 뜻이죠.
✅ 2. 그런데 이미 이건 아래 for문에서 처리돼요
for t in range(target, num - 1, -1):
dp[t] = dp[t] or dp[t - num]→ 여기서 t == num일 때 보면:
dp[num] = dp[num] or dp[0]→ dp[0]은 항상 True로 초기화돼 있으니까
→ 결과적으로 dp[num] = True가 됩니다!
즉, num 하나로 target을 만드는 경우는 아래 for문이 알아서 처리해줘요.
✅ 3. 결론
- dp[num] = True라는 초기화는 for문에서 자동 처리됨
- 그래서 별도로 if로 체크해서 True로 바꿔줄 필요 없음
- 이 라인은 중복이며 제거해도 정확하게 동작합니다.