[Backtracking, Medium] Combination Sum III

https://leetcode.com/problems/combination-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75

일단 k가 n보다 크면 정답이 절대로 될 수 없으므로 바로 리턴

backtrack은 재귀적으로 수행하는데, List<Integer>형태의 콤비네이션을 계속 가지고 다녀야 할 듯.

답이 될 수 있는 조건은 combination.size() == k 이면서, 합이 n과 같아야 하는데
이걸 매번 for문 돌려가면서 sum을 구할 필요는 없을 것 같고
n값을 변경해 가면서 체크하면 될 것 같다. (넣은 원소는 빼기)

그러면 최종적으로 combination.size() == k && n == 0일 때 answer에 넣어주면 됨
백트래킹으로 원소를 넣었다 뺐다 하므로 answer에 더할 때는 인스턴스를 새로 만들어 줘야 한다.

backtrack 내부 구현은
start ~ 9 까지 for문을 돌면서 combination에 더하고 재귀 호출
start는 변동되는 값. 처음에는 1로 시작

오름차순으로 수행하기 때문에 중복없음 보장

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (k > n) {
            return result;
        }

        backtrack(new ArrayList<>(), 1, k, n, result);
        return result;
    }

    private void backtrack(List<Integer> combination, int start, int k, int n, List<List<Integer>> result) {
        if (combination.size() == k && n == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i=start; i<=9; i++) {
            if (n - i < 0) {
                break;
            }

            combination.add(i);
            backtrack(combination, i + 1, k, n - i, result);
            combination.remove(combination.size() - 1);
        }
    }
}