Combination Sum

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

Combination Sum - LeetCode

 

타겟의 합계를 맞추기 위해 알맞은 요소의 조합을 찾는 문제이다.
전형적인 DFS 백트래킹 문제로 조건들을 문제에 맞춰 해결 해주면 된다. 크게 특이사항은 없는 문제였다.

class Solution {  
  
    static int[] candidates;  
    static int target;  
    static List<List<Integer>> answer;  
  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {  
        this.candidates = candidates;  
        this.target = target;  
        this.answer = new ArrayList<>();  
        List<Integer> init = new ArrayList<Integer>();  
        for(int i = 0; i < candidates.length; i++){  
            init.add(candidates[i]);  
            dfs(0, i, init);  
            init.remove(0);  
        }  
  
        return answer;  
    }  
  
    private void dfs(int sum, int idx, List<Integer> list){  
        int curCandidate = candidates[idx];  
        sum += curCandidate;  
        if(sum == target){  
            answer.add(new ArrayList<>(list));  
            return;  
        }  
  
        // 중복 조합을 피하기위해 현재 idx보다 높은 경우만 체크  
        for(int i = idx; i < candidates.length; i++){  
            int nextCandidate = candidates[i];  
            if(nextCandidate + sum > target) continue;  
  
            list.add(nextCandidate);  
            int curListIdx = list.size() - 1;  
            dfs(sum, i, list);  
            list.remove(curListIdx);  
        }  
    }  
}