[leetcode] Medium-39번. Combination Sum 문제풀이

문제

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

Combination Sum - LeetCode

 

 

 

 

풀이코드

package SITE03_leetcode.medium;

import SITE03_leetcode.common.ListNode;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * https://leetcode.com/problems/generate-parentheses/
 */
public class M016_leetcode39_CombinationSum {
    List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    int target;
    int[] map;

    public static void main(String[] args) {
        M016_leetcode39_CombinationSum solution = new M016_leetcode39_CombinationSum();

        int[] dx = {2,7,6,3,5,1};

        System.out.println(solution.combinationSum(dx, 9));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        /* 정렬 */
        Arrays.sort(candidates);

        this.map = candidates;
        this.target = target;

        List<Integer> addList = new ArrayList<Integer>();
        dfs(0, 0, addList);
        return resultList;
    }

    public void dfs(int start, int sum, List<Integer> addList) {
        // 탈출조건
        if (sum == target) {
            resultList.add(new ArrayList<>(addList));
        }

        if (sum < target) {
            for (int i = start; i < map.length; i++) {
                sum = sum + map[i];

                if (sum > target) {
                    // 합계가 target 보다 커진다면 아웃
                    break;
                } else {
                    // 합계가 target 보다 작다면 실행
                    addList.add(map[i]);

                    dfs(i, sum, addList);

                    // 호출이 끝나면 다시 되돌리기
                    addList.remove(addList.size() - 1); // add 됬던 addList 제자리
                    sum = sum - map[i]; // 더해졌던 sum 제자리
                }
            }
        }
    }
}