Partition Equal Subset Sum
양의 정수 배열 nums가 주어집니다. 값들을 합이 같은 두 그룹으로 나눌 수 있는지 판단하세요. 각 값은 정확히 하나의 그룹에 들어가며, 그룹은 어떤 위치에 있는 값이든 포함할 수 있습니다. 그러한 분할이 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
함수
- numsinteger-array
- 양수 값을 두 그룹으로 나누기
- 반환값boolean
- 값을 합이 같은 두 그룹으로 나눌 수 있으면 true, 그렇지 않으면 false
제약 조건
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100
예제
- 입력
- nums = [6, 1, 4, 9, 2]
- 출력
- true
- 설명
- 합계는 22이므로 각 그룹에는 11이 필요합니다. 9 + 2와 6 + 1 + 4는 모두 11이므로 답은
true입니다.
- 입력
- nums = [4, 7, 2, 9, 6]
- 출력
- false
- 설명
- 총합은 28이므로 각 그룹에는 14가 필요합니다. 9개를 가진 그룹에는 5개가 더 필요하지만, 4, 7, 2, 6을 어떻게 조합해도 5를 만들 수 없으므로 총합이 짝수인데도 답은
false입니다.
- 입력
- nums = [1, 2, 3, 5]
- 출력
- false
- 설명
- 합계는 11입니다. 서로 같은 두 정수의 합은 항상 짝수이므로, 홀수인 합계는 절대로 둘로 나눌 수 없으며 답은
false입니다.
제출 시 숨은 테스트 +18개
후속 질문
동일하게 나눌 수 없을 때, 두 그룹 합의 차이를 가능한 한 작게 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
두 그룹의 합이 같다면,
nums의 전체 합을 기준으로 각 합은 얼마여야 할까요? 그리고 전체 합이 홀수라면 무엇을 바로 알 수 있을까요?전체의 절반이 되는 한 그룹만 찾으면 됩니다. 남은 값들은 다른 그룹을 이룹니다. 처음 몇 개의 값으로 만들 수 있는 합의 집합과 값이 하나 더 추가되면 그 집합이 어떻게 달라지는지 생각해 보세요.
reach[0..target]불리언 배열을 유지하고,reach[0]만 true로 둡니다. 각 값num에 대해s를target부터num까지 거꾸로 순회하며,reach[s-num]이 표시되어 있으면reach[s]를 표시합니다. 거꾸로 순회하면 각 값을 두 번 사용하지 않게 됩니다.
풀이
각 그룹은 전체의 정확히 절반을 가져야 하므로, 실제로 확인해야 할 것은 nums의 어떤 부분집합의 합이 target = total / 2인지입니다. 모든 부분집합을 시도하면 2^n의 비용이 들기 때문에 값이 200개일 때는 현실적으로 불가능합니다. 하지만 합 자체는 작습니다. target은 최대 200 × 100 / 2 = 10^4입니다. 도달 가능한 합을 값 하나씩 기록하면, 탐색을 O(n × sum) 단계로 채워지는 0/1 배낭 테이블로 바꿀 수 있습니다.
재귀를 사용해 모든 부분 집합을 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
전체 합부터 시작하세요. 전체 합이 홀수라면 두 개의 같은 정수의 합은 짝수이므로 분할할 수 없습니다. 그렇지 않다면 각 그룹의 합은 정확히 target = total / 2여야 합니다. target을 만드는 값들을 찾으면, 선택하지 않은 값들이 나머지 절반을 저절로 만듭니다. 따라서 한 가지 질문이면 충분합니다. 어떤 부분집합이 target에 도달할 수 있을까요?
값을 순서대로 살펴보며 각 값에 대해 첫 번째 그룹에 넣거나 두 번째 그룹에 남겨 두는 선택을 합니다. 도우미 함수 reach(i, remaining)는 인덱스 i부터 끝까지의 값으로 remaining을 만들 수 있는지 답합니다. remaining이 0이 되면 true를 반환하고, 값이 더 이상 없거나 0보다 작아지면 false를 반환하며, 그렇지 않으면 nums[i]에 대해 두 가지 선택을 모두 시도합니다.
모든 부분집합은 하나의 선택 경로에 해당하므로 탐색은 분할 방법을 놓칠 수 없고, 답은 정확합니다. 하지만 경로가 2^n개이기 때문에 느리며, 분할 방법이 없는 입력에서는 거의 모든 경로를 시도해야 합니다. 100이 199개이고 98이 하나 있다고 해 봅시다. 전체 합은 19998이고, 목표값 9999에는 결코 도달하지 못하며, 탐색은 100을 최대 99개까지 고르는 모든 방법을 시도합니다. 경로 수는 약 4 × 10^59개입니다. 값이 40개만 있어도 2^40, 즉 약 10^12개의 경로가 생깁니다.
알고리즘
nums의 값을 모두 더합니다. 합계가 홀수이면false를 반환합니다.target을 합계의 절반으로 설정합니다.reach(i, remaining)을 작성합니다.remaining이 0이면 true를 반환하고,i가 마지막 값의 인덱스를 넘었거나remaining이 0보다 작으면 false를 반환합니다.- 그렇지 않으면
reach(i+1, remaining-nums[i])또는reach(i+1, remaining)을 반환합니다. 값을 선택하거나 건너뜁니다. reach(0, target)을 반환합니다.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
# Can some of the values from index i on add up to exactly remaining?
def reach(i, remaining):
if remaining == 0:
return True
if i == len(nums) or remaining < 0:
return False
# Put nums[i] in the first group, or leave it for the second one
return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)
return reach(0, total // 2)값과 합계를 표에 채우기
핵심 아이디어
재귀 호출은 같은 질문을 반복해서 합니다. reach(i, remaining)은 두 숫자에만 의존합니다. 0부터 n까지의 i와 0부터 target까지의 remaining입니다. 따라서 서로 다른 질문은 최대 (n+1) × (target+1)개이며, 제한값에서는 약 201 × 10001 ≈ 2 × 10^6개입니다. 이는 모든 질문에 한 번씩 답하기에 충분히 적은 수입니다.
표에서 답을 앞에서부터 채워 나갑니다. can[i][s]는 처음 i개의 값 중 일부를 더해 s를 만들 수 있는지를 나타냅니다. 값이 하나도 없으면 합계 0만 가능하므로, 0행에서는 can[0][0]을 제외한 모든 값이 false입니다. 값 num = nums[i-1]을 사용하면 s에 도달하는 방법은 두 가지입니다. num을 빼서 이전 값들만으로 이미 s에 도달하거나, num을 넣어서 이전 값들로 s-num에 도달하는 것입니다. 이것이 전체 규칙입니다. can[i][s] = can[i-1][s] or can[i-1][s-num]이며, 두 번째 항은 s ≥ num일 때만 고려합니다. 각 행은 바로 위 행만 참조하므로 각 값은 최대 한 번만 사용됩니다.
target이 11인 [6, 1, 4, 9, 2]에서는 만들 수 있는 합계가 {0}에서 {0, 6}으로, 이어서 {0, 1, 6, 7}로, 그다음 {0, 1, 4, 5, 6, 7, 10, 11}로 늘어납니다. 4를 처리한 뒤 합계 11(6 + 1 + 4)이 나타나고, 이후 행에서도 유지됩니다. 답은 can[n][target]입니다. 각 셀을 계산하는 데 일정한 작업량이 들기 때문에 시간과 메모리 모두 O(n × target)입니다.
알고리즘
- 전체 합이 홀수이면
false를 반환하고target을 전체 합의 절반으로 설정합니다. - 모든 값이 false인 n+1개의 행과 target+1개의 열로 이루어진 표를 만들고,
can[0][0]을 true로 설정합니다. - 1부터 n까지 각 행
i에 대해num = nums[i-1]을 가져옵니다. - 0부터
target까지 각 합s에 대해can[i][s]를can[i-1][s]또는,s ≥ num인 경우can[i-1][s-num]으로 설정합니다. can[n][target]을 반환합니다.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
n = len(nums)
# can[i][s] is True when some of the first i values add up to s
can = [[False] * (target + 1) for _ in range(n + 1)]
can[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# Leave num out, or put it in and reach s - num with the values before it
can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
return can[n][target]위에서 아래로 채워지는 덧셈 한 줄
핵심 아이디어
표의 각 행은 바로 위 행만 읽으므로, 제자리에서 갱신하면 행 하나로 충분합니다. reach[s]는 지금까지 확인한 값 중 일부의 합이 s인지 나타냅니다. 주의할 점은 갱신 순서입니다. s를 작은 값에서 큰 값으로 순회하면 reach[s-num]이 같은 num에 의해 이미 켜졌을 수 있습니다. [3, 9]와 목표값 6의 경우, 3이 reach[3]을 표시한 다음 이를 읽어 reach[6]을 표시하므로, 마치 3이 두 개 있는 것처럼 됩니다. 그러면 존재하지 않는 분할을 가능하다고 답하게 됩니다.
target에서 num까지 s를 큰 값에서 작은 값으로 순회하세요. 그러면 s-num은 더 작은 인덱스이며, 아직 이 값이 건드리지 않았으므로 reach[s-num]에는 num이 들어오기 전의 답이 그대로 남아 있습니다. 이는 표의 can[i-1][s-num]과 정확히 같으며, 행 하나로 표 전체의 작업을 수행할 수 있습니다.
reach[target]이 true가 되는 순간 멈춰도 됩니다. 이후의 값은 도달 가능한 합을 추가하기만 할 뿐, 기존 합을 제거하지는 않기 때문입니다. 최악의 경우에도 단계 수는 여전히 O(n × target), 즉 약 2 × 10^6이고, 메모리 사용량은 target + 1개의 불리언 값으로 줄어듭니다.
알고리즘
- 홀수 합계이면
false를 반환하고target을 그 절반으로 설정합니다. target + 1개의 항목으로reach를 만들고,reach[0]만 true로 하고 나머지는 모두 false로 설정합니다.- 각 값
num에 대해s를target부터num까지 감소시키며 순회하고,reach[s-num]가 true이면reach[s]를 true로 설정합니다. - 각 값을 처리한 후
reach[target]이 true이면true를 반환합니다. - 루프가 끝나면
reach[target]을 반환합니다. 이 값은 false입니다.
def canPartition(nums):
total = sum(nums)
if total % 2 == 1:
return False
target = total // 2
# reach[s] is True when some of the values seen so far add up to s
reach = [False] * (target + 1)
reach[0] = True
for num in nums:
# Walk the sums downward so num is used at most once
for s in range(target, num - 1, -1):
if reach[s - num]:
reach[s] = True
if reach[target]:
return True
return reach[target]
함정과 경계 사례
여기서 오답이 나오는 이유는 탐욕적인 규칙을 믿거나, 홀수인지 확인하는 과정을 건너뛰거나, 한 행 테이블에서 값을 재사용하기 때문입니다.
- 한 행 버전에서 합을 작은 값부터 순회하면 값을 두 번 이상 사용하게 됩니다.
[3, 9]에서 목표값은 6입니다. 3은 합 3을 표시한 다음 합 6도 표시하므로 true라고 답하게 됩니다. - 홀수인지 확인하는 과정을 건너뛰는 경우입니다.
[1, 2]의 합계 3을 내림하면 목표값은 1이고, 값 1이 목표값에 도달하므로 실제로는 존재할 수 없는 분할에 대해 true라고 답하게 됩니다. - 정렬한 뒤 항상 더 작은 그룹에 값을 더하는 식의 탐욕적인 채우기는
[3, 3, 2, 2, 2]에서 실패합니다. 한쪽은 7, 다른 쪽은 5가 되지만, 실제로는 3 + 3 = 2 + 2 + 2입니다. [2, 2, 2, 10]처럼 목표값보다 큰 값이 있는 경우입니다.target에서num까지 내려가는 루프는 0회 실행되는데, 이는 올바른 동작입니다. 하지만 R에서(num+1):(target+1)과 같은 범위는 역순으로 계산되어 테이블이 깨집니다. 이런 값은 건너뛰세요.- 합계가 짝수라는 것만으로는 충분하지 않습니다.
[4, 7, 2, 9, 6]의 합은 28이지만 여전히 분할할 수 없습니다. - Lua와 R의 배열은 1부터 시작하므로, 합
s에 해당하는 항목은 인덱스s + 1에 있습니다.
자주 묻는 질문4
Partition Equal Subset Sum은 왜 0/1 배낭 문제인가요?
크기가 target = total / 2인 배낭이 있고, 각 값을 최대 한 번씩 사용하여 정확히 채워야 합니다. 각 값을 선택하거나 선택하지 않는 것이 0/1 선택이며, 값의 크기는 그 값 자체입니다. 도달 가능한 합을 기록하는 배낭 테이블을 사용하면 O(n × target) 시간에 답을 구할 수 있습니다.
Partition Equal Subset Sum의 시간 복잡도는 얼마인가요?
테이블 방식은 target이 전체의 절반일 때 O(n × target)의 시간이 걸리며, 한 행만 사용하면 O(target)의 메모리가 필요합니다. 최댓값이 100인 값이 200개라면 약 2 × 10^6단계입니다. 이 상한은 값의 개수뿐만 아니라 값의 크기에 따라서도 커지므로 의사 다항 시간이라고 합니다. 값이 10^9에 가까우면 테이블을 만들 수 없으며, 일반적인 문제는 NP-완전입니다.
내부 루프는 왜 목표값에서 값까지 거꾸로 진행하나요?
아래로 순회한다는 것은 이 값이 reach[s-num]을 변경하기 전에 먼저 읽는다는 뜻이므로, 여전히 num 이전의 값을 나타냅니다. 위로 순회하면 num을 사용해 만든 합에 다시 num을 더할 수 있어서, 하나의 값이 여러 번 계산됩니다. 동전 교환 문제처럼 무제한으로 사용할 수 있는 경우에는 위로 순회하는 루프가 맞지만, 여기서는 틀립니다.
Partition Equal Subset Sum을 비트셋으로 풀 수 있나요?
네. 도달 가능한 합을 하나의 큰 수의 비트로 저장하고, 처음에는 비트 0만 설정합니다. 각 값에 대해 bits |= bits << num은 그 값을 모든 도달 가능한 합에 한 번에 더하며, 답은 비트 target이 설정되어 있는지 여부입니다. 같은 표를 사용하지만, 각 머신 워드가 한 번에 64개의 합을 처리하므로 실제로 훨씬 빠르게 실행됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def canPartition(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [6, 1, 4, 9, 2]
기대값
true