소소한 개발일지

문제

중복되지 않은 숫자 후보인 배열과 integer 타겟이 주어지고, 숫자 후보들을 선택해 만든 조합의 합이 타겟이 되는 중복되지 않는 조합들의 list를 반환해야 합니다. 조합은 어떤 순서로 반환해도 됩니다.

같은 숫자를 몇 번이든 선택해도 좋습니다. 두 조합이 있을 때, 선택된 숫자의 횟수가 다르다면 중복되지 않는 조합이라고 할 수 있습니다.

더해서 타겟이 되는 조합의 수는 150개 미만으로 테스트케이스가 주어집니다.

예시

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

2와 3이 후보라면, 2 + 2 + 3 = 7. 2가 여러 번 사용 되었습니다.
7이 후보라면, 7 = 7.
두 조합 밖에 없습니다.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

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

주어진 후보에서 1을 만들 수 있는 조합은 없습니다.

풀이 : Backtracking

문제를 봤을 때 직관적으로 푼다면 제일 작은 숫자를 최대한 선택하고 타겟이 되는지 확인하고, 된다면 해당 조합을 저장하면 될 것 같았다.

그 후 넣었던 작은 숫자를 빼고 그 다음 큰 숫자를 넣어보는 방식으로 처리하면 될 것 같다 생각했다.

물론 합이 타겟을 넘어도 다음 숫자를 넣을 만큼 기존 숫자를 빼야한다.

예시 1번 이라면 2를 4번까지 넣었을 때 8이기에 다음으로 큰 숫자인 3을 넣을 수 있게 2개를 뺀 후 넣으면 첫번째 조합인 [2, 2, 3]이 된다.

처음에는 for 문으로 작성하면 될려나 했지만, 가능은 하겠지만 조건식이 복잡할 것 같다는 생각이 들어 recursive한 방식으로 진행하는게 좋다고 생각났다. 처음 생각한 아이디어에서 크게 벗어나지 않고 깔끔하게 코드를 작성해 보았다.

recursive 하게 첫 숫자 후보부터 모든 숫자를 넣어 합이 타겟이 되는지 확인한다.

합이 타겟이 된다면 해당 조합을 저장한다.

합이 타겟보다 크면 해당 조합에서는 어떤 숫자를 더 넣어도 타겟보다 클테니 그 전의 조합으로 돌아간다.

합이 타겟보다 작으면 해당 조합에 숫자 후보를 한 번 더 넣어서 recursive 하게 조합을 추가한다.

코드는 아래와 같습니다.

class Solution {
    List<Integer> comb = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public void combination(int[] candidates, int target, int idx) {
        if (target < 0) return ;
        if (target == 0) {
            ans.add(new ArrayList<>(comb));
            return ;
        }

        for (int i = idx; i < candidates.length; i++) {
            comb.add(candidates[i]);
            combination(candidates, target - candidates[i], i);
            comb.remove(comb.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combination(candidates, target, 0);
        return ans;
    }
}

참고로 조합의 합을 확인하는 방식이 아니라 처음 타겟에서 숫자 후보를 계속 빼서 0이 되는지 아닌지 확인하는 방식으로 진행했습니다.

모든 조합을 추출하되, 어떤 조건에서는 더 추출할 필요가 없는지 조건을 걸면 되는 전형적인 backtracking 문제였습니다.

의견 및 질문은 늘 환영합니다 :)