[LeetCode] 39. Combination Sum - 브루트포스(BruteForce) JAVA

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

코드설명

브루트포스(BruteForce) 를 활용합니다.

 

말그대로 모든 조합을 탐색해서, target = 7이 나오도록 처리합니다.

코드

import java.util.*;
class Solution {
    List<List<Integer>> answer = new ArrayList<List<Integer>>();
    int[] Candidates;
    int Target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Candidates = candidates;
        Target = target;
        DFS(0, 0, new ArrayList<Integer>());
        return answer;
    }

    void DFS(int level, int sum, ArrayList<Integer> list){
        if(sum == Target){
            ArrayList<Integer> newList = new ArrayList<Integer>(list);
            answer.add(newList);
            return ;
        }
        if(level == Candidates.length){
            return ;
        }

        if(sum + Candidates[level] <= Target){
            list.add(Candidates[level]);
            DFS(level, sum + Candidates[level], list);
            list.remove(list.size() - 1);
        }
        DFS(level + 1, sum, list);
    }
}