LeetCode 494. Target Sum(JAVA)

출처 : https://leetcode.com/problems/target-sum/description/?envType=daily-question&envId=2024-12-26

#문제

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.

정수 배열 nums와 정수 target이 주어집니다.nums의 각 정수 앞에 '+' 또는 '-' 기호를 추가하여 표현식을 만들고자 합니다.그런 다음 이 표현식을 모두 이어붙입니다.
예를 들어, nums = [2, 1]일 때, 2 앞에 '+'를, 1 앞에 '-'를 추가하여 "+2-1"과 같은 표현식을 만들 수 있습니다.
이 표현식의 값이 target과 같아지는 서로 다른 표현식의 개수를 반환하세요.

 

접근 : DFS

DFS를 통해 모든 +,-  조합을 탐색하여 카운팅

class Solution {
     public int findTargetSumWays(int[] nums, int target) {
        int[] res = {0};
        dfs(nums,0,target,0,res);
        return res[0];
    }
    private void dfs(int[] nums, int i,int target, int sum,int[] res) {
        if(i == nums.length) {
             if(sum == target) {
                res[0]++;
             }
             return;
        }
        dfs(nums, i+1, target, sum + nums[i],res);
        dfs(nums, i+1, target, sum - nums[i],res);
    }
}

 

접근 : DFS +  Memoization

DFS탐색중 각각의 레벨에서의 target을 완성할수있는 경우의 수를 저장하여 탐색효율성을 늘린다

public class Solution {
    int totalSum = 0;
    public int findTargetSumWays(int[] nums, int target) {
        int[] res = {0};
        for (int num : nums){
            totalSum += num;
        }
        int[][] memo = new int[nums.length][totalSum*2+1];
        for (int[] m : memo){
            Arrays.fill(m, Integer.MIN_VALUE);
        }
        return dfs(nums,0,target,0,memo);
    }
    private int dfs(int[] nums, int i,int target, int sum,int[][] memo) {
        if(i == nums.length) {
             if(sum == target) {
                return 1;
             }
             return 0;
        }
        if(memo[i][sum+totalSum] != Integer.MIN_VALUE) {
            return memo[i][sum+totalSum];
        }
        int add =  dfs(nums, i+1, target, sum + nums[i],memo);
        int minus = dfs(nums, i+1, target, sum - nums[i],memo);
        memo[i][sum+totalSum] = add + minus;
        return memo[i][sum+totalSum];
    }
}

 

왜 totalSum*2+1 인가? 

dfs탐색을통해 누적값이 음수일경우를 처리하기위해 전체합(totalSum)*2+1의 크기만큼 선언, 때문에 누적값이 -totalSum이라도 다루는것이 가능해짐

 

memo[i][sum+totalSum] 의 뜻

현재 인덱스(i)에서 현재 합(sum) 일때 target에 도달할수있는 경우의 수

 

모든범위의 합을 다루기위해 sum+totalSum이라했지만 그냥 memo[i][sum] 으로 생각하는것이 조금더 편함.

ex) nums = [1,1,1,1,1] , target = 3일때

sum+totalSum = 3 이라면 memo[4][3] ==> memo[4][-2] 로 생각 남은연산은 +1 or -1 이고 현재 sum == -2 이므로 memo[4][-2] = 0 이 될것임