[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);
}
}
}
'알고리즘 > 코딩테스트-NeetCode' 카테고리의 다른 글
[NeetCode-LeetCode] Max Area of Island JAVA (0) | 2025.02.26 |
---|---|
[NeetCode-LeetCode] Koko Eating Bananas Java (0) | 2025.02.25 |
[NeetCode-LeetCode] Last Stone Weight JAVA (1) | 2025.02.12 |
[NeetCode-LeetCode] Search a 2D Matrix JAVA (0) | 2025.02.11 |
[NeetCode-LeetCode] Daily Temperatures JAVA (0) | 2025.02.10 |