[LeetCode] 77. Combinations - 백트래킹

오늘의 학습 키워드

백트래킹

 

알고리즘 문제

LeetCode Medium - 77. Combinations

 

 

공부했던 내용

Back Tracking

• 특징
  • 가능한 모든 조합을 시도한다.
  • 조건을 만족하지 않으면 탐색을 중단하고, 이전 단계로 돌아가서 진행한다.
• 핵심
  • 선택 -> 탐색 -> 선택 취소

---

회고

• 백트래킹의 재귀 호출과 재귀 종료 후 이전 단계로 돌아가는 부분이 헷갈렸다.
• 선택 -> 재귀 호출로 모든 조합 탐색 -> 각 탐색 종료 시 선택 취소 => 이 부분을 정확히 이해해야 했다.

---

문제 풀이

import java.util.List;
import java.util.ArrayList;

class Solution {
    public void dfs(int start, int n, int k, List<Integer> comb, List<List<Integer>> result) {
        if (comb.size() == k) {
            result.add(new ArrayList<>(comb));
            return;
        }

        for (int i = start; i <= n; i++) {
            comb.add(i);
            dfs(i+1, n, k, comb, result);
            comb.remove(comb.size()-1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        
        List<List<Integer>> result = new ArrayList<>();
        
        dfs(1, n, k, new ArrayList<Integer>(), result);

        return result;
    }
}

 

 

github

Algorithm-Practice/LeetCode/0077-combinations/0077-combinations.java at main · dev-jinius/Algorithm-Practice