Target Sum
음수가 아닌 정수 배열 nums와 정수 target이 주어집니다. 모든 숫자 앞에 더하기 또는 빼기 기호를 붙이고, 순서를 유지한 채 식을 계산합니다. 식의 값이 target이 되도록 하는 기호 선택의 수를 반환하세요. 2^n가지 선택은 각각 별도로 계산되므로 +0과 -0은 서로 다른 두 가지 선택입니다.
함수
- numsinteger-array
- 각각 부호가 붙는 숫자들
- targetinteger
- 식이 같아야 하는 값
- 반환값integer
- 식의 값이 target과 같은 부호 선택의 수
제약 조건
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- The sum of
nums은 최대 1000입니다. -1000 ≤ target ≤ 1000- 정답은 최대 220으로, 32비트 부호 있는 정수의 범위 안에 충분히 들어갑니다.
예제
- 입력
- nums = [2, 1, 1]target = 2
- 출력
- 2
- 설명
+2 +1 -1과+2 -1 +1은 둘 다 2입니다. 2에 마이너스를 붙이면 도달할 수 있는 최댓값은 -2 + 1 + 1 = 0이므로, 다른 선택지는 없습니다.
- 입력
- nums = [0, 4, 4]target = 0
- 출력
- 4
- 설명
- 두 개의 4에는 서로 반대 부호가 필요합니다.
+4 -4또는-4 +4이며, 두 경우 모두 0은 어느 부호를 가져도 됩니다. 따라서 2 × 2 = 4가지 선택이 가능합니다.
- 입력
- nums = [6, 3]target = 4
- 출력
- 0
- 설명
- 가능한 네 가지 값은 9, 3, -3, -9입니다. 부호를 뒤집으면 합계가 그 수의 두 배만큼 바뀌므로, 모든 결과는 6 + 3 = 9처럼 홀수이며 짝수인 목표값 4에는 도달할 수 없습니다.
후속 질문
합을 인덱스로 하는 배열이 메모리에 들어가지 않는 상황에서, 값이 최대 10^9인 숫자를 최대 40개까지 처리할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 숫자에 두 가지 부호를 모두 적용해 볼 수 있으며, 그러면 표현식은
2^n개가 됩니다. 서로 다른 부호 접두사가 같은 누적 합으로 이어지는 경우가 많고, 그 시점부터는 동작이 완전히 같다는 점에 주목하세요.더하기 기호가 붙는 숫자들의 합을
P, 빼기 기호가 붙는 숫자들의 합을N이라고 하세요.P - N = target이고P + N = sum(nums)임을 알고 있습니다. 이로부터P에 대해 무엇을 알 수 있나요?P = (sum + target) / 2이므로, 그 값의 합이 되는nums의 부분집합 개수를 세세요.s에 도달하는 부분집합의 개수인ways[s]를 유지하고, 각 숫자에 대해 가장 큰s부터 내려가며 업데이트하세요.sum + target이 홀수이거나|target| > sum이면 즉시 0을 반환하세요.
풀이
각 숫자에는 두 가지 부호가 있으므로 2^n개의 식이 있습니다. 위치와 누적 합을 기준으로 세면 같은 합에 도달하는 부호 접두사를 하나로 합칠 수 있습니다. 더 나아가, 양수 부호가 붙은 숫자들은 합이 고정된 부분집합을 이루므로, 문제는 주어진 합을 가진 부분집합의 개수를 세는 것으로 바뀌며, nums의 합인 S에 대해 O(n × S) 시간에 해결할 수 있습니다.
모든 숫자에 대해 두 부호를 모두 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
누적 합계를 유지하면서 숫자를 왼쪽에서 오른쪽으로 살펴보고, 각 숫자마다 두 가지로 분기하세요. 더하거나 빼면 됩니다. 모든 숫자에 부호를 붙였을 때 합계가 target과 같으면 1을 셉니다. 각 부호 선택은 정확히 하나의 경로이므로, 그 개수를 모두 더하면 답이 됩니다.
각 선택마다 리프 노드가 하나씩 생깁니다. 숫자가 20개이면 2^20 ≈ 10^6개의 리프 노드가 생기고, 숫자가 하나 늘어날 때마다 작업량은 두 배가 됩니다.
알고리즘
count(i, total)은i이전의 숫자들의 합이 이미total일 때nums[i..]에 부호를 붙이는 방법의 수입니다.i == n이면total == target일 때 1을 반환하고, 그렇지 않으면 0을 반환합니다.- 그렇지 않으면
count(i+1, total + nums[i]) + count(i+1, total - nums[i])을 반환합니다. - 정답은
count(0, 0)입니다.
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)위치와 누적 합계를 기준으로 메모이제이션
핵심 아이디어
count(i, total)은 i와 total에만 의존하며, total을 만들어 낸 부호에는 의존하지 않습니다. nums = [1, 1, 1, 1]일 때, 접두 부분 +1 -1과 -1 +1은 모두 위치 2에서 total 0에 도달하므로, 그 지점부터의 탐색은 동일합니다. 각 결과를 처음 계산할 때 저장하고 재사용하세요.
누적 합은 -S와 S 사이에 있으므로, 인덱스로 사용하려면 S만큼 더해 이동시키면 됩니다: memo[i][total + S]. 상태는 최대 n × (2S+1)개이며, 합이 1000인 숫자 20개인 경우 약 4 × 10^4개이고, 각 상태에서 수행하는 작업은 상수 시간입니다.
알고리즘
S = sum(nums)를 계산하고 -1로 채워진n × (2S+1)메모 배열을 만듭니다.count(i, total)에서 이전과 같이i == n일 때 기본 사례를 반환합니다.memo[i][total + S]가 -1이면count(i+1, total + nums[i]) + count(i+1, total - nums[i])로 채웁니다.- 저장된 값을 반환하고
count(0, 0)을 호출합니다.
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)(S + target) / 2의 합이 되는 부분집합의 개수를 세세요
핵심 아이디어
P를 더하기 부호가 붙은 수들의 합이라고 하고, N을 나머지 수들의 합이라고 하겠습니다. 그러면 P - N = target이고 P + N = S이므로 2P = S + target입니다. 부호를 선택했을 때 더하기 그룹의 합이 (S + target) / 2인 경우에만 조건을 만족하며, 이러한 각 부분집합은 하나의 부호 선택에 해당합니다.
ways[s]는 지금까지 확인한 수 중 합이 s인 부분집합의 개수를 셉니다. 처음에는 ways[0] = 1입니다. 각 수 x에 대해, 합이 s인 부분집합은 x를 건너뛰거나 합이 s - x인 부분집합에 더할 수 있습니다. s를 큰 값부터 내려가며 처리하면 ways[s - x]에는 여전히 x를 처리하기 전 값이 남아 있으므로 같은 수를 두 번 사용하지 않습니다. 0은 모든 항목을 자기 자신에 더해 모든 개수를 두 배로 만듭니다. 이는 0에 두 가지 부호를 붙이는 경우입니다. 총 n × goal번의 덧셈이며, 최대 2 × 10^4번입니다.
알고리즘
S = sum(nums)를 계산합니다.|target| > S이거나S + target이 홀수이면 0을 반환합니다.goal = (S + target) / 2로 설정하고,goal + 1개의 0으로ways를 만들고ways[0] = 1로 설정합니다.nums의 각x에 대해goal에서x까지 거꾸로s를 순회하며ways[s - x]를ways[s]에 더합니다.ways[goal]을 반환합니다.
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
함정과 경계 사례
- 패리티 검사를 건너뜁니다.
[6, 3]에서 목표가 4일 때(9 + 4) / 2는 내림하여 6이 되고, 부분집합{6}은 0 대신 1을 반환합니다. - 범위 검사를 건너뜁니다.
[1, 2, 3]에서 목표가 -10일 때(6 - 10) / 2 = -2가 되어 배열 크기가 음수가 됩니다. ways를 상향식으로 채웁니다. 그러면 숫자가 이미 자신을 사용하는 부분집합에 합류합니다. 목표가 2인[1, 3]은 1 대신 2를 반환합니다.- 0을 하나의 선택으로 취급합니다. 목표가 -1인
[0, 0, 0, 1, 0, 0]에는 32개의 답이 있습니다. 이는 0 다섯 개의 모든 부호 패턴에 해당합니다. - 음수 누적 합을 사용해 메모를 인덱싱합니다. 모든 합에
S를 더해 이동시키거나 해시 맵을 사용하세요.
자주 묻는 질문3
Target Sum은 부분집합 합 문제와 어떤 관련이 있나요?
더하기 기호가 붙은 숫자들의 합은 (S + target) / 2여야 하므로, 답은 합이 그 값인 nums의 부분집합 개수입니다. 부분집합 합을 세는 동적 계획법으로 이 문제를 해결할 수 있으며, 두 가지 조건을 추가해야 합니다. 값이 정수여야 하고, |target|이 S를 초과해서는 안 됩니다.
Target Sum의 시간 복잡도는 얼마인가요?
부분집합 개수 세기 DP는 O(n × S) 시간과 O(S) 메모리를 사용하며, 여기서 S는 nums의 합입니다. 메모이제이션을 적용한 재귀도 시간은 동일하지만 n × (2S+1) 테이블을 사용합니다. 모든 부호 조합을 시도하면 O(2^n)입니다.
Target Sum은 누적 합계를 저장하는 해시 맵으로 풀 수 있을까요?
네. 도달 가능한 각 누적 합을 그 값에 도달하는 부호 접두사의 개수에 대응시키고, {0: 1}에서 시작합니다. 그런 다음 각 숫자에 대해 total + x와 total - x를 사용해 다음 맵을 만듭니다. 정답은 target의 개수입니다. 이는 메모이제이션된 재귀를 정방향으로 실행하는 것으로, 동일하게 O(n × S) 시간에 수행됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def findTargetSumWays(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [2, 1, 1] target = 2
예상 출력
2