[LeetCode] 40. Combination Sum II - 깊이우선탐색(DFS) + 해시셋(HashSet) JAVA

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

코드설명

깊이우선탐색(DFS) + 해시셋(HashSet) 를 활용합니다.

 

처음에는 모든 경우를 완전탐색한뒤, HashSet을 활용하여 중복코드를 제거했습니다만, 시간초과가 발생합니다.

 

이를 해결하기 위해(HashSet 없이 중복제거를 하기 위해), 아래코드를 활용합니다.

if(i > level && candidates[i] == candidates[i - 1]) continue;

이를 통해, 현재 값이 이전값과 같을 경우 건너뜁니다. 이를 통해 이미 선택한 값을 다시 선택하지 않게 만듭니다.

i > level을 통해 첫번쨰 선택시에는 무시하고, 두번쨰 선택부터 candidates[i] == candidates[i-1]로 비교하여 처리합니다. 

코드

중복제거한 코드입니다.

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target){
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(candidates);
        DFS(candidates, target, 0, 0, new ArrayList<>(), answer);
        return answer;
    }
    void DFS(int[] candidates, int target, int level, int sum, List<Integer> arr, List<List<Integer>> answer){
        if(sum == target){
            ArrayList<Integer> temp = new ArrayList<>();
            for(int v : arr){
                temp.add(v);
            }
            answer.add(temp);
            return ;
        }

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

            if(candidates[i] + sum <= target){
                arr.add(candidates[i]);
                DFS(candidates, target, i + 1, candidates[i] + sum, arr, answer);
                arr.remove(arr.size() - 1);
            }
        }
    }


}

 

 

처음에 시간초과 난 코드입니다. 이 방식의 경우, 중복된 숫자를 건너뛰지 못하는 로직을 구현하지 못합니다.

class Solution {
    //time complexity O(2^50)
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(candidates);
        DFS(candidates, target, 0, 0, new ArrayList<>(), answer, new HashSet<>());
        return answer;
    }
    void DFS(int[] candidates, int target, int idx, int sum, ArrayList<Integer> arr, List<List<Integer>> answer, HashSet<String> hashset){
        if(sum == target){
            ArrayList<Integer> newArr = new ArrayList<Integer>();
            StringBuilder sb = new StringBuilder();
            for(int v : arr){
                sb.append(v);
                newArr.add(v);
            }
            if(hashset.contains(sb.toString()) == false){
                hashset.add(sb.toString());
                answer.add(newArr);
            }
            return ;
        }
        if(idx == candidates.length) return ;
        
        if(candidates[idx] + sum <= target){
            arr.add(candidates[idx]);
            DFS(candidates, target, idx + 1, candidates[idx] + sum, arr, answer, hashset);
            arr.remove(arr.size() - 1);
        }
        DFS(candidates, target, idx + 1, sum, arr, answer, hashset);
    }
}