What is the best way to solve Target Sum?

The optimized O(1) approach using 2D DP patterns is generally preferred.

상위 150개 인터뷰중간

목표합계

'Target Sum' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

정수 배열 nums와 정수 목표가 제공됩니다.

nums의 각 정수 앞에 '+' 및 '-' 기호 중 하나를 추가한 다음 모든 정수를 연결하여 nums로 표현식을 작성하려고 합니다.

목표로 평가되는 빌드할 수 있는 다양한 표현식의 수를 반환합니다.

findTargetSumWays(nums: List[int], target: int) -> int 함수를 작성하세요.

제약

•1 <= len(nums) <= 20
•0 <= nums[i] <= 1000
•0 <= sum(nums) <= 1000
•-1000 <= target <= 1000

예

Example 1

Input

nums = [1,1,1,1,1], target = 3

Output

Explanation

There are 5 ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.

Example 2

Input

nums = [1], target = 1

Output

Explanation

+1 = 1

Need a Hint?

세트나 힙과 같은 2D DP 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

2D DP 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def find_target_sum_ways_opt(nums, target):
    dp = {} # (index, total)
    def backtrack(i, total):
        if i == len(nums): return 1 if total == target else 0
        if (i, total) in dp: return dp[(i, total)]
        dp[(i, total)] = backtrack(i + 1, total + nums[i]) + backtrack(i + 1, total - nums[i])
        return dp[(i, total)]
    return backtrack(0, 0)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def find_target_sum_ways_brute(nums, target):
    def solve(i, cur):
        if i == len(nums): return 1 if cur == target else 0
        return solve(i + 1, cur + nums[i]) + solve(i + 1, cur - nums[i])
    return solve(0, 0)