https://leetcode.com/problems/combination-sum/
✅ 체크 포인트
1. ArrayList를 깊은 복사 : ArrayList<>(comb);
2. Backtracking할 때 다음 시작 인덱스를 i
를 해야할까 i + 1
을 해야할까?
제출 코드
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> answer = new ArrayList<>();
Arrays.sort(candidates);
dfs(answer, new ArrayList<>(), candidates, target, 0);
return answer;
}
private static void dfs(List<List<Integer>> answer, ArrayList<Integer> comb, int[] candidates, int target, int start) {
if (target < 0) return;
if (target == 0) {
answer.add(new ArrayList<>(comb));
return;
}
for (int i=start; i<candidates.length; i++) {
int cur = candidates[i];
comb.add(cur);
dfs(answer, comb, candidates, target - cur, i);
comb.remove(comb.size() - 1);
}
}
}
효율성
'Algorithm' 카테고리의 다른 글
BOJ 11727. 2×n 타일링 2 - JAVA (0) | 2024.06.16 |
---|---|
[Python] 백준 7662 : 이중 우선순위 큐 (0) | 2022.11.02 |
[Python] 구름LEVEL : 개미와 진딧물 (0) | 2022.11.01 |
[Python] 백준 3190 : 뱀 (implementation) (2) | 2022.10.07 |
[Python] 백준 1865 : 웜홀 (Bellman Ford) (0) | 2022.10.04 |