LeetCode: 40번 (Combination Sum II) [JAVA]

문제 링크

https://leetcode.com/problems/combination-sum-ii/

Combination Sum II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 candidates 배열을 돌며 중복과 target보다 큰 수를 제거, 중복의 경우 따로 개수를 세서 저장(HashMap)
2. 이후 새로 생성한 candidates 리스트를 정렬(오름차순)
3. 완전 탐색
   1) 파라미터의 경우 candidates 리스트 속 index, target 중 현재 까지의 값들을 제외한 나머지(remain), 임시 저장용 List
   2) remain이 0미만이거나 index가 candidates 리스트 밖인 경우 탐색 종료. remain이 0이면 그때 결과를 답에 저장
   3) 현재 candidates 리스트 속 숫자를 아예 안넣거나 중복 개수만큼 임시 저장용 List에 넣은 다음에 이후 탐색 call
4. 결과 반환

 문제에서는 단순히 주어진 candidats 배열 속 숫자들의 조합으로 target을 만들 수 있는 조합을 모두 만들어 반환해야 한다. 이런 경우 대체적으로 완전 탐색을 진행하기 때문에, 새로운 로직을 적용하기 보단 활용할 데이터를 다듬는 방향으로 진행했다.
 우선 주어진 candidates 배열을 돌며 중복과 target보다 큰 수를 제거한다. 중복의 경우엔 따로 개수를 HashMap 형태로 저장한다. 그리고 그 결과물로 나온 candidates 리스트를 오름차순으로 정렬해준 다음, 완전탐색을 진행한다. 우선 완전 탐색 함수의 경우 인자로 candidates 리스트 속 위치를 지정한 index, target에서 여태까지의 숫자를 뺀 나머지인 remain, 적용된 숫자들을 임시로 저장해놓은 리스트 set이다. 탐색 종료 조건으로는 index가 candidates 리스트를 벗어나거나 remain이 0이하인 경우이며, remain이 딱 0이라면 그때의 set 속 숫자들을 답에 저장한다. 그 다음엔 candidates 리스트 속 index 위치의 숫자와 해당 숫자가 중복된 개수를 가져온 다음 탐색을 진행한다. 현재 숫자를 아예 넣지 않거나 최대 중복 개수만큼 넣은 다음에 index+1 위치로 탐색을 반복한다. 그리고 탐색이 끝나면 set의 최신화를 위해 해당 숫자들을 제거해준다.

 

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    HashMap<Integer, Integer> candidateCount = new HashMap<>();
    List<Integer> candidatesList = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        for (int i = 0; i < candidates.length; i++) {//candidates 배열 정리 -> 중복 & 큰 수 제거
            if (candidates[i] <= target) {
                if (!candidateCount.containsKey(candidates[i])) {
                    candidateCount.put(candidates[i], 1);
                    candidatesList.add(candidates[i]);
                } else {
                    candidateCount.replace(candidates[i], candidateCount.get(candidates[i]) + 1);
                }
            }
        }

        Collections.sort(candidatesList);

        search(0, target, new ArrayList<>());//탐색

        return answer;
    }

    void search(int index, int remain, List<Integer> set) {
        if (remain <= 0 || index >= candidatesList.size()) {//탐색 종료 조건
            if (remain == 0) {
                answer.add(new ArrayList<>(set));
            }
            return;
        }

        int candidate = candidatesList.get(index);
        int count = candidateCount.get(candidate);

        for (int i = 0; i <= count; i++) {//중복되는 개수 만큼 탐색
            for (int j = 1; j <= i; j++) {
                set.add(candidate);
            }

            search(index + 1, remain - candidate * i, set);

            for (int j = 1; j <= i; j++) {
                set.remove((Integer) candidate);
            }
        }
    }
}

결과