알고리즘/코딩테스트-NeetCode

[NeetCode-LeetCode] Combination Sum II JAVA

kwang2134 2025. 2. 24. 20:53
728x90
반응형
728x90

[NeetCode-LeetCode] Combination Sum II - Medium 


접근

  • dfs 

풀이

주어진 배열 내 숫자들을 한 번씩만 사용해 target 값을 만들 수 있는 조합을 모두 찾아내는 문제이다. 숫자들은 한 번씩만 사용이 가능하며 중복된 조합은 포함하면 안 된다. 

 

단순하게 dfs를 사용해 모든 경우를 탐색하면 되는데 목표로 맞춰야 하는 값이 존재하기 때문에 그 값을 기준으로 백트래킹을 통한 불필요한 값을 걸러주면 되는 문제이다. 

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);

        dfs(candidates, result, new ArrayList<>(), 0, target);


        return result;
    }

백트래킹을 효과적으로 적용하기 위해 주어진 배열을 먼저 정렬해 줬다. target 보다 큰 값이 나오거나 다음 값을 추가했는데 target을 넘어선다면 그 뒤에 있는 모든 값들에 대해 탐색이 불필요하여 반복을 줄일 수 있다. 

    public void dfs(int[] candidates, List<List<Integer>> result ,List<Integer> current, int index, int target) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

dfs를 수행하는 부분인데 이 문제처럼 target 값을 맞춰야 한다면 따로 더한 값을 target과 비교하는 것보다 target의 값을 감소시키는 게 편하다. target의 값이 0이 된다면 목표하는 값을 맞출 수 있는 조합이 현재 배열에 들어있는 것으로 조합을 추가하고 해당 구간 탐색을 종료한다. 

	for (int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i-1]) continue;
            if(candidates[i] > target) break;

            current.add(candidates[i]);
            dfs(candidates, result, current, i + 1, target - candidates[i]);
            current.remove(current.size() - 1);
        }
    }

조합을 만드는 부분인데 첫 번째 if 문을 통해 중복된 조합을 제거해 주는 코드가 중요하다. 똑같은 숫자에서 시작하는 조합은 모두 동일하기 때문에 같은 숫자에 대해선 한 번의 반복만 수행해 주면 되기 때문이다. 현재 배열은 정렬된 상태이고 똑같은 숫자가 존재한다면 연속으로 나오기 때문에 [5, 5, 5]처럼 5가 연속으로 나오는 경우에는 첫 번째 5에 대한 조합만 탐색하고 뒤에 나오는 두 개의 5에 대해선 탐색을 수행하지 않고 건너뛰는 것이다. 나머지 코드는 현재 추가할 값이 target 보다 크다면 더 이상 탐색이 불 필요해 종료하고 그렇지 않다면 값을 추가하고 다음 단계로 넘어간다. 


전체 코드

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);

        dfs(candidates, result, new ArrayList<>(), 0, target);


        return result;
    }

    public void dfs(int[] candidates, List<List<Integer>> result ,List<Integer> current, int index, int target) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i-1]) continue;
            if(candidates[i] > target) break;

            current.add(candidates[i]);
            dfs(candidates, result, current, i + 1, target - candidates[i]);
            current.remove(current.size() - 1);
        }
    }
}
728x90