리트코드) 39.조합의 합(자바)

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

문제 : 고유한 정수 배열 candidates과 대상 정수가 주어 지면 선택한 숫자 의 합이 가 되는 모든 고유 조합 목록을target 반환하라

입력 : [2,3,6,7], target = 7 출력 : [[2,2,3],[7]]

• 총 합이 target이 되는 조합 갯수와 상관없이 전부 리스트에 담기
• 조합을 뽑아서, 더해보고, target과 같으면 반환
• 동일한 번호는 여러번 무제한 사용할 수 있음

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
class Solution {
        
     List<List<Integer>> result;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        result = new ArrayList<List<Integer>>();
        dfs(new ArrayDeque<>(), candidates, target, 0);
        return result;
    }

    public void dfs(Deque<Integer> temp, int[] candidates, int target, int idx) {
        if(target < 0) {
            // 실패
            return;
        }
        if(target == 0) {
            // 성공
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i=idx; i<candidates.length; i++) {
            temp.add(candidates[i]);
            dfs(temp, candidates, target-candidates[i], i);
            temp.removeLast();
        }
    }
}