[LeetCode] 39. Combination Sum

문제 설명

문제 풀이

Back Tracking을 이용하여 풀이하였다. 직관적으로 candidates들을 하나씩 방문하며 각각 N번씩 더해주고 다음 인덱스로 넘어가는 방식으로 index == candidates.length일 때를 기저 조건으로 두고 모든 경우를 판별하였다.

소스 코드 (JAVA)

class Solution {
    private List<List<Integer>> result;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> temp = new ArrayList<>();
        result = new ArrayList<>();
        combinationSum(candidates, temp, 0, target);
        return result;
    }
    
    public void combinationSum(int[] candidates, List<Integer> cur, int index, int target) {
        if (index == candidates.length) {
            if (target == 0) result.add(new ArrayList(cur));
            return;
        }
        int cnt = -1;
        while(candidates[index] * ++cnt <= target) {
            for (int i = 0; i < cnt; i++) cur.add(candidates[index]);
            combinationSum(candidates, cur, index + 1, target - candidates[index] * cnt);
            for (int i = 0; i < cnt; i++) cur.remove(cur.size() - 1);
        }
    }