Leetcode - Combination Sum II [Java]

문제 출처: https://leetcode.com/problems/combination-sum-ii/

문제 설명

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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

문제 풀이

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> answer = new ArrayList<>();
        backtracking(0, target, candidates, new LinkedList<Integer>(), answer);
        return answer;
    }
    
    public void backtracking(int start, int target, int[] candidates, LinkedList<Integer> cur, List<List<Integer>> answer) {
        if(target == 0) {
            answer.add(new ArrayList<Integer>(cur));
        } else {
            for(int i = start; i < candidates.length; i++) {
                if(i > start && candidates[i] == candidates[i - 1]) continue;
                if(target - candidates[i] < 0) return;
                cur.addLast(candidates[i]);
                backtracking(i + 1, target - candidates[i], candidates, cur, answer);
                cur.removeLast();
            }
        }
    }
}

배열 안의 숫자는 1번씩만 사용할 수 있는데 tricky한 부분은 duplicate number가 있다는 것이다.

재귀 호출을 할때 i -> i + 1으로 넘기기 때문에 tracker는 필요하지 않았다. 대신 중복 숫자에 대한 처리가 필요했는데, 해결한 방법은 다음과 같다.

주어진 배열[10,1,2,7,6,1,5]을 정렬한다. ---> [1,1,2,5,6,7,10]

배열이 재귀적으로 호출될때 바로 두번째 루프를 탈때부터 바로 이전의 인덱스와 같은지 비교한다.

쉽게 말해서,

재귀로 넘어온 호출의 for loop의 시작 인덱스가 1이라면 그 스택안에서 인덱스 2로 넘어간 후 부터 검사를 한다.

ex)

중복 포함 경우

남은배열 [1,1,2,5,6,7,10] ---> [1] 담고 재귀 호출

두번째 루프에서 두가지 경우

1. 남은배열 [1,2,5,6,7,10] (인덱스를 1부터 시작할거라 첫번째 element가 없어졋다고 가정) ---> [1,1] 담고 재귀 호출

2. 남은배열 [1,2,5,6,7,10] (인덱스를 1부터 시작할거라 첫번째 element가 없어졋다고 가정) ---> [1,1] 담고 재귀 호출 후 다시 삭제한 다음 두번째 루프 탐 [1]

   남은배열 [2,5,6,7,10] (인덱스를 1부터 시작할거라 첫번째 element가 없어졋다고 가정) ---> [1,2] 담고 재귀 호출

중복 제거 경우

남은배열 [1,1,2,5,6,7,10] ---> [1] 담고 재귀 호출 후 다시 삭제한 다음 두번째 루프 탐 []

남은배열 [1,2,5,6,7,10] ---> 두번째 루프에서 candidates[i] == candidates[i - 1] 이라서 넘어감 []

결과적으로 1,1 또는 1,2가 중복으로 발생되는 경우가 해결됨