[Java] LeetCode 39번 Combination Sum

[Java] LeetCode 39번 Combination Sum

DP를 이용해서 해결하였다. map에 key는 숫자, value에는 더해서 key를 만들 수 있는 리스트를 저장하였다.

0부터 target까지 만들 수 있는 숫자의 조합을 계속 더해가면서 문제를 해결하엿다.

class Solution { public List> combinationSum(int[] candidates, int target) { Map>> map = new HashMap<>(); for (int i = 0; i <= target; i++) { for (int j = 0; j < candidates.length; j++) { int idx = i - candidates[j]; // 후보 숫자와 전에 있는 숫자들과 더해서 i 가 되는 경우 if (idx >= 0) { List> beforeList = map.get(idx); if (beforeList != null) { List> curList = map.getOrDefault(i, new ArrayList<>()); for (int k = 0; k < beforeList.size(); k++) { List list = new ArrayList<>(); list.addAll(beforeList.get(k)); // 중복을 피하고 오름차순으로 후보군을 만들기 위함이다. if (candidates[j] >= list.get(list.size() - 1)) { list.add(candidates[j]); curList.add(list); } } if (!curList.isEmpty()) map.put(i, curList); } } // 후보 숫자가 바로 i 가 되는 경우 if (i == candidates[j]) { List> curList = map.get(candidates[j]); if (curList == null) { curList = new ArrayList<>(); } List item = new ArrayList<>(); item.add(candidates[j]); curList.add(item); map.put(candidates[j], curList); } } } return map.getOrDefault(target, new ArrayList<>()); } }

반응형

from http://blue-jay.tistory.com/84 by ccl(A) rewrite - 2021-10-04 13:01:33