LeetCode 39. Combination Sum

https://leetcode.com/problems/combination-sum/

 

✅ 체크 포인트

1. ArrayList를 깊은 복사 :  ArrayList<>(comb);

2. Backtracking할 때 다음 시작 인덱스를 i 를 해야할까 i + 1 을 해야할까?

 

제출 코드

class Solution {
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(answer, new ArrayList<>(), candidates, target, 0);
        
        return answer;
    }
    
    private static void dfs(List<List<Integer>> answer, ArrayList<Integer> comb, int[] candidates, int target, int start) {
        
        if (target < 0) return;
        
        if (target == 0) {
            answer.add(new ArrayList<>(comb));
            return;
        }
        
        for (int i=start; i<candidates.length; i++) {
            int cur = candidates[i];
            comb.add(cur);
            dfs(answer, comb, candidates, target - cur, i);
            comb.remove(comb.size() - 1);
        }
    }
}

 

효율성