[LeetCode] Combination sums 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Combination sums

---

 
문제 요약

정수 배열 candidates 와 정수 target 이 주어질 때, 중복 선택이 가능한 숫자들로 합이 target이 되는 모든 조합을 구하는 문제

같은 숫자를 여러 번 사용 가능, 조합은 순서가 다르면 같은 조합으로 취급, 모든 조합 반환

 
문제링크: https://leetcode.com/problems/combination-sum 
 
 

🤔 처음에는 이렇게 생각했다

처음 이 문제를 봤을 때,
솔직히 큰 알고리즘 트릭이 있는 문제처럼 보이진 않았다.

“숫자들을 중복해서 쓸 수 있고,
합이 target이 되는 경우를 전부 찾으라면
그냥 모든 조합을 만들어보고 합이 맞으면 넣으면 되는 거 아닌가?”

그래서 자연스럽게 브루트포스가 먼저 떠올랐다.
 
DFS로 숫자를 하나씩 더해가면서,
합이 target이 되면 결과에 추가하는 방식이다.
 
그런데 바로 한 가지가 마음에 걸렸다.
시간복잡도였다.
 
모든 경우를 다 만들어보는 방식이면
탐색 공간이 너무 커질 것 같다는 느낌이 들었다.

---

💡 핵심 아이디어

 

이 문제를 다시 보면서 가장 먼저 정리해야 했던 건 이것이다.

 

이 문제는 “순열”이 아니라 “조합”이다.

 [2,2,3] == [2,3,2] == [3,2,2]

• 순서가 중요하지 않다
• 같은 숫자를 여러 번 쓸 수는 있지만
  이미 지나온 숫자로 돌아가면 안 된다

👉 그래서 탐색할 때는 이전 인덱스보다 앞에 있는 숫자는 다시 보지 않는다.

 

이 한 가지 규칙이 중복 조합을 제거하는 핵심 제약이 된다.

---

🧠 사고 흐름 정리 (DFS 설계)

DFS를 코드부터 짜려고 하면 쉽게 꼬인다.
이 문제에서는 설계를 먼저 말로 정리하는 게 중요했다.

 

① 상태 (State)

DFS 한 번의 호출이 표현하는 정보는 다음과 같다.

• 지금까지 선택한 숫자들 (nums)
• 남은 target 값
• 다음에 선택할 수 있는 시작 인덱스 (curIdx)

상태: dfs(target, 시작 인덱스, 현재 조합)

 

② 종료 조건 (Base Case)

• target == 0 → 하나의 조합 완성 → 결과에 추가
• target < 0 → 더 볼 필요 없음 → 종료

③ 선택지 (Choices)

• 현재 숫자를 선택한다 (같은 인덱스 curIdx 유지)
• 현재 숫자를 선택하지 않고 다음 숫자로 넘어간다 (curIdx + 1)

④ 제약 (Pruning)

불필요한 탐색을 줄이기 위한 조건들이다.

• target이 음수가 되는 순간 즉시 종료
• curIdx 이전의 숫자는 다시 보지 않음 → 중복 제거
• (정렬 후) target < candidates[curIdx] 이면 더 볼 필요 없음

⑤ 다음 단계로 넘길 정보

• 줄어든 target
• 유지하거나 증가한 curIdx
• 현재까지의 선택 결과 (nums)

 

DFS 구조 한눈에 보기

dfs(target, curIdx, nums)
├─ target == 0
│    └─ 하나의 조합 완성 → 결과에 추가
│
├─ target < 0
│    └─ 더 이상 진행 불가 → return
│
├─ 현재 숫자 선택
│    ├─ nums.add(candidates[curIdx])
│    └─ dfs(target - cur, curIdx)   // 같은 숫자 재사용
│
└─ 현재 숫자 선택 안 함
     └─ dfs(target, curIdx + 1)      // 다음 숫자로 이동​

 

 

💡 핵심 포인트 요약

• curIdx 이전 숫자는 다시 보지 않음 → 중복 제거
• 같은 숫자를 여러 번 쓰기 위해 curIdx 유지
• 선택 후에는 반드시 되돌리기 (Backtracking)

---

 

코드 (Java)

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);

        List<List<Integer>> results = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), results);
        return results;
    }

    private void dfs(
            int[] candidates,
            int target,
            int curIdx,
            List<Integer> nums,
            List<List<Integer>> results
    ) {
        // 성공 종료
        if (target == 0) {
            results.add(new ArrayList<>(nums)); // 반드시 복사
            return;
        }

        // 실패 종료
        if (curIdx >= candidates.length || target < candidates[curIdx]) {
            return;
        }

        // 선택: 현재 숫자 사용
        nums.add(candidates[curIdx]);
        dfs(candidates, target - candidates[curIdx], curIdx, nums, results);
        nums.remove(nums.size() - 1); // backtracking

        // 선택 안 함: 다음 숫자로 이동
        dfs(candidates, target, curIdx + 1, nums, results);
    }
}

 

 

📈 Time / Space Complexity

• 이 문제는 모든 가능한 조합을 탐색해야 하므로 지수 시간이다.
  
  • 대략적: O(N^(target/min)) 👉 하지만 백트래킹으로 불필요한 경로는 조기에 차단 (아래 자세한 시간복잡도 설명)
  • O(N^(T / min))
    - N: 후보 숫자 개수
    - T: Target 
    - min : candidates 중 최솟값
    - T/min: 최대 DFS 깊이
    👉 target이 커질수록 기하급수적으로 증가
    
    좀 더 느슨한 표현
    O(2^T)
    - 각 단계마다 선택 / 비선택
    - 깊이가 T에 비례
    
    O(2^T) 는 target을 1씩 줄어드는 추상 단위로 본 매우 느슨한 상한이고,
    O(N^(T / min)) 은 실제 DFS 깊이(T / min)를 반영한 구조 기반 상한이다.
• 공간: DFS 호출 스택
  • O(target / min(candidates))

---

 

📝 이번 문제에서 얻은 깨달음

• DFS는 “트리”로 생각해야 한다
  
  • 각 숫자는 선택 / 비선택 두 갈래
  • 문제의 본질은 이 트리를 어디까지 탐색하느냐
• 백트래킹을 써도 되는지 판단하는 3가지 질문

• ① 모든 경우를 한 번씩은 봐야 하는가?
  → YES → 백트래킹 후보
  • “가능한 모든 조합 / 경우의 수를 구하라”
  • “모든 해를 출력하라”

• ② 중간에 답이 될 수 없는 경우를 알 수 있는가?
  → YES → 백트래킹 확정
  • 합이 이미 초과됨
  • 규칙을 위반함
  • 더 진행해도 목표 도달 불가

• ③ 선택 → 되돌리기 패턴인가?
  → YES → DFS / 백트래킹 구조
  • 하나 선택
  • 다음 선택
  • 조건 안 맞으면 취소 

•  
• Java 의 DFS 에서 배열 넘길 때 배열을 복사하자!!! 
  •  results.add(new ArrayList<>(nums)); 👉 참조 그대로 넣으면 결과가 전부 바뀐다.