[LeetCode-자바] N_494 Target Sum

0woy·2025년 1월 14일

DFS Java Map backtracing leetcode memoization

코딩테스트

목록 보기

43/43

📜 문제

숫자가 저장된 배열 (nums)와 목표값 (target)이 주어진다.
배열 내의 모든 숫자를 더하거나 빼서 target을 만들 수 있는 경우의 수 반환

생각하기

처음 문제를 읽고 "내가 이거 풀 수 있나?" 라는 생각이 먼저 듦.
그래서 그냥 배열 끝까지 탐색하고 target 값이 0이 되면 경우의 수 count 올리는 방식으로 접근했다.

🍳 전체 소스 코드 1

class Solution {
        static int count;
    public int findTargetSumWays(int[] nums, int target) {
        count=0;
        dfs(nums, target, 0, 0);
        return count;
    }
      public static void dfs(int [] nums, int target, int idx, int total){
        if(idx == nums.length){
            if(target == total){
                count++;
            }
            return;
        }

        dfs(nums, target, idx+1, total+nums[idx]);
        dfs(nums, target, idx+1, total-nums[idx]);
    }
}

count: 경우의 수
dfs(): 현재 값을 누적값에 더하거나 빼기

이렇게 배열의 끝까지 도달했을 때 target과 누적값(total)이 같으면 count 1증가

풀리긴 풀리는데 시간복잡도가 외딴섬 로맨틱 -> 넘 오래 걸려유

그렇다면.. 중복탐색을 안하게끔 만들어 주면 되겠다~

🍳 전체 소스 코드 2

class Solution {
    static Map<String,Integer> memo;
    public int findTargetSumWays(int[] nums, int target) {
         memo = new HashMap<>();
        int res =dfs(nums, target, 0,0);
        return res;
    }
      public static int dfs(int [] nums, int target, int idx,int total){
        if(idx == nums.length){
            return target == total?1:0;
        }
        if(memo.containsKey(idx+","+total)){
            return memo.get(idx+","+total);
        }

        int res = dfs(nums, target, idx+1,total+nums[idx])
                + dfs(nums, target, idx+1,total-nums[idx]);

        memo.put(idx+","+total, res);
        return res;
    }
}