Leetcode 494. Target Sum

문제

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.

• 정수 배열과 타겟 값이 주어진다.
• 정수 배열의 값들이 양수 혹은 음수가 된다고 할때
• 이들을 적당히 양수/음수로 바꾸어 타겟이 되는 경우의 수를 전부 구하라

예시

[1, 1, 2] => target = 2
(-1) + (1) + (2)
(1) + (-1) + (2)
- 2가지 경우의 수

예시

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

• -1 + 1 + 1 + 1 + 1 = 3
• +1 - 1 + 1 + 1 + 1 = 3
• +1 + 1 - 1 + 1 + 1 = 3
• +1 + 1 + 1 - 1 + 1 = 3
• +1 + 1 + 1 + 1 - 1 = 3
• 총 5가지 경우의 수

제한

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

풀이

1. 백트래킹

• 백트래킹과 memoization을 사용해 풀어봤다.

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        cache = {}

        def backtracking(index: int, value: int):
            if index == len(nums):
                if value == target:
                    return 1
                else:
                    return 0

            if (index, value) in cache:
                return cache[(index, value)]

            a = backtracking(index + 1, value + nums[index]) + backtracking(index + 1, value - nums[index])

            cache[(index, value)] = a

            return a
            
        return backtracking(0, 0)

• lru_cache 를 쓸수도 있다

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        @lru_cache(None)
        def backtracking(index: int, value: int) -> int:
            if index == len(nums):
                return 1 if value == target else 0

            return backtracking(index + 1, value + nums[index]) + backtracking(index + 1, value - nums[index])
        
        return backtracking(0, 0)

• 150ms

dp 방식

• 우리가 제거해야할 숫자들의 합만 알아내서 DP로 구할수도 있다.
• O(n^2) 에 가까운 풀이인데, O(n) 풀이를 찾다 시간을 너무 썼다
• 백트래킹이 memo 없이 O(2^n) 에 가까운걸 생각하면 훨신 낫긴 하다.

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        if (sum(nums) - target) % 2 or (sum(nums) - target) < 0:
            return 0

        remove = (sum(nums) - target) // 2

        dp = [0] * (remove + 1)
        dp[0] = 1

        for num in nums:
            for t in range(remove, num - 1, -1):
                dp[t] = dp[t - num] + dp[t]

        return dp[remove]

• 14ms