문제

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

제한사항

• 1 $\leq$ candidates.length $\leq$ 100
• 1 $\leq$ candidates[i] $\leq$ 50
• 1 $\leq$ target $\leq$ 30

접근

중복된 숫자가 있는 집합에서 모든 값을 더했을 시 target이 되는 부분집합을 구하는 문제에요. 여기선 동일한 원소를 사용하면 안되는 조건이 추가되었어요.

처음엔 그냥 BFS로 간단하게 풀면 되지!해서 풀었는데, 해당 테스트 케이스에서 시간 초과가 발생했어요.

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 27

여기서 보고 힌트를 얻은 것이, 집합을 정렬한 후에 이전의 값과 동일한 값을 넣어서 전개를 하면 중복 처리로 인한 불필요성이 존재하게 되는 것을 깨닳았어요. 그래서 이전에 전개한 값과 똑같다면 처리하지 않는 Backtracking 방식으로 로직을 수정하였더니 해결했어요. 다만 속도는 좀 낮네요. 다른데 보니까 DFS로 Backtracking하니까 더 빠르더라구요.

답안

class Solution {
    
    private class CombinationInfo {
        public int offsetIndex;
        public List<Integer> subset = new ArrayList<>();
        public int total;

    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> answer = new ArrayList<>();        
        Queue<CombinationInfo> queue = new LinkedList<>();

        int prevCandi = 0;
        for(int index = 0; index < candidates.length; ++index){
            if(prevCandi == candidates[index])
                continue;
            
            CombinationInfo info = new CombinationInfo();
            info.offsetIndex = index;
            info.subset.add(candidates[index]);
            info.total = candidates[index];
            queue.add(info);
            prevCandi = candidates[index];
        }

        while(!queue.isEmpty()){
            CombinationInfo info = queue.poll();

            if(info.total == target){
                if(!answer.contains(info.subset)){
                    answer.add(info.subset);
                }
            }

            prevCandi = 0;
            for(int index = info.offsetIndex + 1; index < candidates.length; ++index){
                if(info.total + candidates[index] > target)
                    continue;
                
                if(prevCandi == candidates[index])
                    continue;
                
                CombinationInfo info2 = new CombinationInfo();
                info2.offsetIndex = index;
                info2.subset = new ArrayList<>(info.subset);
                info2.subset.add(candidates[index]);
                info2.total = info.total + candidates[index];
                queue.add(info2);
                prevCandi = candidates[index];
            }
        }

        return answer;
    }
}