Subset Sum Problem
nums에는 양의 정수가 들어 있고, target은 양의 정수입니다. 각 위치의 값을 최대 한 번씩 사용하여 합이 정확히 target이 되도록 일부 값을 선택할 수 있나요? 가능하면 true를 반환하고, 가능한 선택이 없으면 false를 반환하세요.
함수
- numsinteger-array
- 선택할 수 있는 양수 값
- targetinteger
- 선택한 값들의 정확한 합계
- 반환값boolean
- 일부 값의 합이 정확히 target이 되면 true, 그렇지 않으면 false
제약 조건
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
예제
- 입력
- nums = [8, 3, 11, 5, 7]target = 15
- 출력
- true
- 설명
- 8 + 7 = 15이므로 답은
true입니다. 3 + 5 + 7을 선택해도 됩니다. 한 번만 선택하면 충분합니다.
- 입력
- nums = [6, 9, 12, 15]target = 20
- 출력
- false
- 설명
- 모든 값은 3의 배수이므로, 그 값들의 모든 합도 3의 배수입니다. 20은 그렇지 않으므로 답은
false입니다.
- 입력
- nums = [4, 1, 2]target = 8
- 출력
- false
- 설명
- 세 값을 모두 합하면 4 + 1 + 2 = 7로, 8보다 작으므로 어떤 선택으로도 8에 도달할 수 없고 답은
false입니다.
후속 질문
서로 다른 위치에 있는 두 개의 같은 값은 서로 다른 선택으로 간주됩니다. 몇 개의 선택이 target에 도달할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
nums[0]부터 시작하세요. 선택 항목에 이것이 포함되면, 나머지 값들은target-nums[0]이 되어야 합니다. 포함되지 않으면, 나머지 값들은target이 되어야 합니다. 둘 다 더 짧은 배열에서 같은 질문입니다.위치
i부터 시작하는 값들로 합계r을 만들 수 있는지는i와r에만 달려 있으며,r은target을 초과하지 않습니다. 따라서 서로 다른 질문은 최대 약 200 × 10^4개이며, 각 질문은 한 번씩만 답하면 됩니다.0부터
target까지의 각 합에 불리언 값 하나를 사용하고, 처음에는 합 0만 도달 가능하게 합니다. 값을 하나씩 추가합니다.s-num이 이미 도달 가능했다면 합s도 도달 가능해집니다. 값을 두 번 사용하지 않도록 합을 큰 값부터 작은 값 순으로 갱신하고,target에서 답을 읽습니다.
풀이
각 값마다 선택 여부가 있으므로, 값이 200개라면 가능한 선택은 2^200가지입니다. 하지만 target ≤ 10^4까지의 합만 중요합니다. 지금까지의 값들로 만들 수 있는 합을 기록하세요. 새 값이 들어올 때마다 그 크기만큼 기록을 이동하면, 탐색은 n × target 크기의 불리언 테이블이 됩니다.
각 값을 선택하거나 건너뛰기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
canMake(i, remaining)은 위치 i부터의 값들로 정확히 remaining을 만들 수 있는지 확인합니다. nums[i]가 들어맞으면 이를 선택하고, 나머지 값들에 remaining-nums[i]를 남깁니다. 실패하면 이를 건너뜁니다. 선택할 때마다 하나의 경로가 되므로, 가능한 선택이 있으면 탐색은 그 선택을 찾아냅니다.
가능한 선택이 없으면 모든 경로를 살펴봅니다. 3의 배수 200개가 있고 각 값이 최대 300이며 목표값이 9998일 때, 어떤 선택도 성공하지 못하지만 임의의 값 33개는 목표값보다 작습니다. 따라서 경로는 10^37개를 넘습니다.
알고리즘
canMake(i, remaining)을 작성합니다.remaining이 0이면 선택이 완료된 것이므로 true를 반환합니다. 남은 값이 없는데도 아직 만들어야 할 값이 있으면 false를 반환합니다.nums[i] ≤ remaining이고canMake(i+1, remaining-nums[i])가 true이면 true를 반환합니다.- 그렇지 않으면
canMake(i+1, remaining)을 반환합니다. canMake(0, target)을 반환합니다.
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)도달 가능한 합계 표 채우기
핵심 아이디어
재귀는 위치와 0부터 target까지의 남은 합에만 의존하며, 여러 경로가 같은 쌍에 도달합니다. 대신 표를 채우세요. made[i][s]는 처음 i개의 값 중에서 선택한 값의 합이 정확히 s일 때 true입니다. 아무것도 선택하지 않으면 합은 0입니다. num = nums[i-1]일 때, 합 s는 num을 선택하지 않고도 만들 수 있었거나(made[i-1][s]), num이 s-num을 완성할 수 있는 경우(s ≥ num일 때 made[i-1][s-num]) 만들 수 있습니다.
첫 번째 예제에서 8을 처리한 뒤 만들 수 있는 합은 0과 8입니다. 3은 3과 11을 더하고, 11은 14만 더하며, 5는 5와 13을 더하고, 8 + 7은 15에 도달합니다. 제한에 따르면 표에는 201 × 10001개의 셀이 있으며, 단계 수는 약 2 × 10^6입니다.
알고리즘
made를 n+1개의 행과 target+1개의 불리언 값으로 할당하고, 모두 false로 설정합니다. 빈 선택을 나타내기 위해made[0][0]을 true로 표시합니다.- 행
i는 i = 1부터 n까지 값num = nums[i-1]을 처리합니다. - 0부터
target까지 각 합s에 대해made[i][s]를made[i-1][s]로 설정합니다. s ≥ num이고made[i-1][s-num]이 true라면,made[i][s]를 true로 설정합니다.made[n][target]을 반환합니다.
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[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 on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]위쪽에서 업데이트되는 합계의 한 행
핵심 아이디어
각 행은 바로 이전 행만 읽으므로 배열 하나인 made[s]에 저장할 수 있습니다. 위쪽으로 덮어쓰면 값이 자기 자신을 참조하게 됩니다. nums = [5]이고 target이 10일 때, s = 5가 true가 된 다음 s = 10은 새로 기록된 값을 읽어 5를 두 번 사용합니다.
대신 target에서 num까지 역순으로 진행하세요. s-num을 읽으면 아직 순회 중에 다시 쓰지 않은 아래쪽 셀에 접근하므로, num을 처리하기 전 행의 값을 확인합니다. 만들어진 합은 계속 만들어진 상태이므로 made[target]이 true가 되면 바로 멈출 수 있습니다. 메모리는 불리언 값 target + 1개로 줄어듭니다.
알고리즘
made[0]만 true인target + 1개의 불리언으로 이루어진 배열 하나로 시작합니다.- 값을 순서대로 가져옵니다. 각
num에 대해s를target에서num까지 감소시키며 실행합니다. made[s-num]이 true인 곳마다made[s]를 표시합니다.made[target]이 표시되는 즉시true로 종료합니다.- 모든 값을 먼저 다 사용하면 답은
false입니다.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
함정과 경계 사례
- 합계를 오름차순으로 확인하면 값을 두 번 사용하게 됩니다.
[3]으로 목표값 9를 만들 수 있다고 답합니다. made[0] = true를 빠뜨리는 경우입니다. 모든 합계는 빈 선택에서 시작하므로, 모든 답이 false로 나옵니다.- 가장 큰 값부터 고르는 경우입니다. 목표값이 10일 때
[6, 5, 5]에서 6을 고르면 4가 남지만, 어떤 값으로도 만들 수 없습니다. 반면 5 + 5 = 10입니다. [10000]에서 목표값이 1인 경우처럼target보다 큰 값은 아무것도 바꾸지 않아야 합니다. Swift의num...target은 프로그램을 중단시키고 R의(num+1):(target+1)은 역방향으로 세므로, 먼저num ≤ target인지 확인하세요.- Lua와 R에서는 합계
s에 해당하는 항목이 인덱스s + 1에 있습니다.
자주 묻는 질문4
부분집합 합 문제의 시간 복잡도는 무엇인가요?
이 표는 O(n × target) 시간이 걸립니다. 값이 200개이고 target이 10^4일 때 약 2 × 10^6단계가 필요하며, 한 행만 사용하면 메모리를 O(target)으로 줄일 수 있습니다. 비용은 target의 수치 크기에 따라 달라지므로, 이 방법은 유사 다항 시간이며 10^18 같은 target에는 쓸모가 없습니다. 일반적으로 부분집합 합 문제는 NP-완전입니다.
Subset Sum은 Partition Equal Subset Sum 및 0/1 배낭 문제와 어떤 관련이 있나요?
Partition Equal Subset Sum은 합계가 짝수인지 확인한 뒤, target = total / 2를 적용한 Subset Sum입니다. Subset Sum은 각 값의 무게가 그 값 자체인 0/1 배낭 문제이며 배낭을 정확히 채워야 하므로, 테이블에는 최적 값 대신 불리언 값이 저장됩니다.
부분집합 합은 음수와 함께 사용할 수 있나요?
아이디어는 맞지만 위의 코드는 맞지 않습니다. 음수가 있으면 도달 가능한 합은 음수들의 총합부터 양수들의 총합까지이므로, 가장 낮은 합만큼 모든 인덱스를 이동하고 같은 방식으로 행을 채우세요. 남은 합보다 큰 값은 더 이상 건너뛸 수 없습니다.
어떤 값들이 목표를 달성하는지 어떻게 찾나요?
전체 표를 유지하고 made[n][target]에서 시작합니다. 한 번에 한 행씩 위로 올라갑니다. made[i-1][s]가 참이면 nums[i-1]은 필요하지 않았습니다. 그렇지 않으면 기록하고 s에서 뺍니다. 합이 0이 되면 유효한 원소 하나를 선택한 것입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def isSubsetSum(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [8, 3, 11, 5, 7] target = 15
예상 출력
true