문제
https://leetcode.com/problems/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.
리트스가 주어졌을때 각각 원소를 덧셈 또는 뺄셈을 해서 target 값과 일치하는 경우의 수를 구하시오
풀이
모든 경우의 수를 구해야한다.
직관적으로 각 원소마다 덧셈, 뺄셈 을 다 해봐서 일일히 구하는 O(2^N) 방식을 떠올릴 수 있다.
좀 더 개선된 풀이 방식으론 recursive dp 를 사용한 백트래킹을 떠올릴 수 있다.
각 원소를 돌면서 sum을 구해야 함으로 (index, totalSum) 한 쌍으로 생각 해 볼수 있다.
첫 번째 예제인 target = 3 , nums=[1,1,1,1,1] 일때를 생각해보자.
(index: 0, totalSum: 0)
│
│덧셈.
└───(1,1)
│ │ 덧셈.
│ │───(2,2)
│ │뺄셈.
│ └───(2,0)
│ │
│ │
│ │ ...
│ 뺄셈
└───(1,-1)
│덧셈
│───(2,0)
│뻴셈
│───(2,1) ...
...이런 식의 트리 구조를 떠올릴 수 있다. 저것을 이전에 구한 값을 저장하는 캐싱을 안하고 반복하면, brute force 즉 O(2^N) 이 된다 .하지만 각 (인덱스, 지금까지의 합) 을 캐싱하면 시간복잡도는 index * (totalsum의 길이) 가 된다. O(i x T)
각 함수에서 탈출 조건은 index == nums.length 이다 이때 sum == target 이면 정답 캐이스임으로 + 1 증가한다.
자바 코드에서 음수 인덱싱을 피하기 위해 totalSum을 더해줘서 memo에 액세스 하였다.
코드
- 자바
class Solution {
int totalSum ;
public int findTargetSumWays(int[] nums, int target) {
//totalsum using stream
totalSum = Arrays.stream(nums).sum();
// totalSum은 음수가 될수 있음으로 길이를 2배 늘린다.
int [][] memo = new int[nums.length][totalSum * 2 + 1];
for(int[] row : memo)
Arrays.fill(row, Integer.MIN_VALUE);
return helper(nums,0, 0,target, memo);
}
public int helper(int[]nums, int i, int sum ,int target, int [][]memo){
if( i == nums.length){ //finish function.
return sum == target ? 1 : 0 ;
}else{
//remember memo. 음수 인덱싱 피하기위해 totalSum덧셈
if(memo[i][sum+totalSum] != Integer.MIN_VALUE)
return memo[i][sum + totalSum] ;
//더하는 경우의 수를 구한다.
int add = helper(nums, i+1, sum+nums[i], target, memo);
//빼는 경우의 수를 구한다.
int subtract = helper(nums, i+1, sum - nums[i], target,memo);
memo[i][sum+totalSum] = add + subtract;
return memo[i][sum+totalSum];
}
}
}- 파이썬
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = {} # (index, total) 경우의 수
def backtrack(i, total):
#basecase
if i == len(nums):
return 1 if total == target else 0
if(i, total) in dp:
return dp[(i, total)] #이미 해싱되있으면 return
#add case + sub case
dp[(i, total)] = (backtrack(i+1, total + nums[i]) + backtrack(i+1, total - nums[i]) )
return dp[(i, total)]
#call the function
return backtrack(0,0)
