LeetCode 77(Combinations, java)

0. 문제

https://leetcode.com/problems/combinations/

Combinations - LeetCode

 

 

1. 문제 설명

- 문제에서 정수 n과 k가 주어진다.

- 1부터 n까지의 수를 이용하여 중복 없이 k개의 짝을 이루는 모든 조합을 구하는 것이 문제의 핵심이다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 전형적인 back tracking 문제다.

- back tracking은 정답에 부합하는 조건을 가진 후보를 차례대로 탐색하는 방법으로, DFS가 대표적인 방법이다. 

- DFS와 같은 방식으로 접근하면 쉽게 풀 수 있는 문제다.

 

 

b) 두 번째 접근

- 이 문제의 핵심은 어떻게 재귀를 호출할 것이냐가 관건이다.

- 예를 들어 n = 4, k = 2일 때 모든 경우의 수를 구하는 방법을 생각해보자.

- 중복된 조합이나 중복 사용된 숫자가 없어야 하므로 다음과 같이 계산할 수 있다. 

   → 1일 때, [1,2] [1,3] [1,4]

   → 2일 때, [2,3] [3,4] 

   → 3일 때, [3,4] 

 

- 위의 과정을 보면 이중 반복문으로 쉽게 구현할 수 있겠다는 생각이 들 것이다.

- 그 규칙을 찾았다면 이중 반복문에서 두 번째 반복문을 재귀로 대체하면 된다.

 

- 다음 코드를 보면서 이해해보자.

 

3. 정답 코드

import java.util.Arrays;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        
        List<List<Integer>> result = new ArrayList<>();
        backTrack(result, new ArrayList<>(), 1, n, k);
        return result;
        
    }   
    
    public void backTrack(List<List<Integer>> result, ArrayList<Integer> sub, int start, int n, int k) {
        if(sub.size() == k) { // 재귀 종료 조건
            result.add(new ArrayList(sub));
            return;
        }
        
        for(int i = start; i <= n && sub.size() < k; i++) {
            sub.add(i);
            backTrack(result, sub, i + 1, n, k);
            sub.remove(sub.size() - 1); 
            // 마지막으로 추가된 요소를 지워야 계속해서 반복문으로 탐색 가능
            // 핵심은 반복문이 종료될 때까지 조합을 계속해서 만드는 것
        }
        return;
    }
}