문제

Combination Sum - LeetCode

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> candidatesList = Arrays.stream(candidates).boxed().collect(Collectors.toList());
        dfs(candidatesList, target, 0, new LinkedList<>(), result);
        return result;
    }

    public void dfs(List<Integer> candidates, int target, int sum, LinkedList<Integer> curr, List<List<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<>(curr));
            return;
        } else if (sum > target) return;

        for (int i = 0; i < candidates.size(); i++) {
            curr.add(candidates.get(i));
            dfs(candidates.subList(i, candidates.size()), target, sum + candidates.get(i), curr, result);
            curr.removeLast();
        }
    }
}

• 항상 자신보다 큰 숫자값들만 탐색함으로써 탐색의 범위를 줄였다.
  - ex) 현재 탐색 2 → 다음 탐색 2부터 시작 (1 제외)
  

다른 풀이 (Runtime: 2ms)

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List < List < Integer >> ans = new ArrayList < > ();
        findCombinations(0, candidates, target, ans, new ArrayList < >());
        return ans;

    }
    private static void findCombinations(int ind, int[] arr, int target, List < List < Integer >> ans, List < Integer > ds) {
       if (ind == arr.length) {
            if (target == 0) {
                ans.add(new ArrayList < > (ds));
            }
            return;
        }

        if (arr[ind] <= target) {
            ds.add(arr[ind]);
            findCombinations(ind, arr, target - arr[ind], ans, ds);
            ds.remove(ds.size() - 1);
        }
        findCombinations(ind + 1, arr, target, ans, ds);
        
    }
}

• arr[ind]가 현재 남아있는 target보다 작다면 더하고 한번 더 호출한다. (중복이 가능하기 때문)
• 더 크다면 다음 ind로 넘어간다.
• 탐색이 끝나면 target이 0인 경우 정답에 추가한다.