[LeetCode] Combination Sum II (Java)

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

Combination Sum II - LeetCode

사용 알고리즘 : 백트래킹(Backtracking)

 

문제 : 입력(후보) 배열이 주어지면 후보 번호의 합계가 target에 해당하는 후보에서 모든 고유 한 조합을 찾습니다. 후보자의 각 숫자는 조합에서 한 번만 사용할 수 있습니다.

 

접근 아이디어 :

1. 백트래킹 알고리즘을 이용하여 target보다 크거나 같은 경우의 수를 모두 찾는다. (순서는 상관없기 때문에 조합)

2. 모든 후보들의 합계를 target과 비교한다. (초과시 함수 종료, 같으면 결과에 포함되는 답이다)

3. 결과에 포함되는 답은 중복이 있을 수 있기 때문에 Set 자료구조를 사용한다.

 

Example 1 : Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

Example 2 : Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]

 

class Solution {
        
    Set<List<Integer>> set = new HashSet<>();
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(new ArrayList<>(), candidates, 0, target, -1);
        return new ArrayList<>(set);
    }
    
    public void backtrack(List<Integer> list, int[] candidates, int sum, int target, int compare) {
        if(sum > target) return;
        if(sum == target) {
            List<Integer> ret = new ArrayList<>();
            for(int num : list) ret.add(num);
            set.add(ret);
            return;
        }
        
        for(int i=0; i<candidates.length; i++) {
            if(compare < i) {
                list.add(candidates[i]);
                backtrack(list, candidates, sum + candidates[i], target, i);
                list.remove(list.size() - 1);
            }
        }
    }
}