리트코드 - 77. Combinations

리트코드 - 77. Combinations

출처 - https://leetcode.com/problems/combinations/description/

 

문제 설명

두 정수 n과 k가 주어졌을 때, 1부터 n까지의 범위에서 k개의 숫자를 선택하는 모든 가능한 조합을 반환하세요.
답은 어떤 순서로든 반환해도 좋습니다.

 

의사코드

함수 combine(n, k):     answer = new ArrayList<>()     combine 함수를 재귀적으로 호출하여 조합을 생성 (answer, 빈 리스트, 시작점 1, n, k)     answer 리턴 함수 combine(answer, current, start, n, k):     if (current.length == k)         answer에 current의 복사본 추가         break     반복문 시작 (start부터 n까지)         current에 i 추가         combine 함수를 i+1, n, k와 함께 재귀적으로 호출         current에서 마지막 요소 제거     반복문 종료

 

풀이코드

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> answer = new ArrayList<>();
        combine(answer, new ArrayList<>(), 1, n, k);

        return answer;
    }

    private void combine(List<List<Integer>> answer, List<Integer> current, int start, int n, int k) {
        if (current.size() == k) {
            answer.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i <= n; i++) {
            current.add(i);
            combine(answer, current, i + 1, n, k);
            current.remove(current.size() - 1);
        }
    }
}

 

코드설명

조합이란 수학적으로 n개에서 k개의 원소를 가지는 경우의 수이다.

예를 들어 4C2 라면 4개에서 2개의 원소를 가지는 경우의 수이고 이 경우 {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}로 총 6개가 된다.

 

{1,2}와 {2,1}은 같은 부분집합으로 보기 때문에 내림차순인 경우는 고려하지 않아도 된다.

따라서 앞에서부터 작은수를 넣고 k를 만족하면 더하면 되기 때문에 재귀가 적합하다.

 

재귀를 사용할 때에는 종료조건을 설정해두는 것이 가장 중요하므로, current의 크기가 k일 때 배열을 복사해서 answer배열에 추가해주도록 하였다.

 

그리고 아래 for문을 통해 current 배열에 값을 넣고 빼고를 재귀적으로 반복한다.

세번째 파라미터를 통해 값을 넣고 빼고를 반복하여 부분집합을 구한다.

 

이제, 로직을 따라가 볼 건데 이해를 위하여 4C2로 예를 들면, n=4, k=2가 될 것이다.

 

1. 첫번째 combine 메소드를 들어갈 땐 아무 것도 들어간게 없으므로 current 크기가 0이라 if문을 지나친다.

이후 for문 안에서 current에 1이 추가될 것이다.

다시 다음줄에서 combine 메소드를 들어가는데 i보다 1 큰 수, 여기서는 2가 파라미터(=start)로 전달된다.

 

2. 전달만 되었을 뿐 추가된 게 아니므로 current 크기가 1 이므로 if문을 또 지나친다.

이제 for문에서 i가 2부터이므로 2가 current에 추가되고, 다음줄에서 combine함수 파라미터로 3이 전달된다.

 

3. 역시 3이 전달되었을 뿐 추가된 것은 아닌데, current 크기가 2로 if문에서 배열이 복사되어 answer에 추가되고 return된다.

 

4. 빠져나온 곳은 2번의 for문 안이다. 2번의 for문에서 current에는 {1, 2}가 들어있다. 

current.remove(current.size() - 1)를 통해 배열 마지막을 지우고 for문을 이어나간다.

 

5. for문에 의해 current에는 3이 추가되어 {1, 3}이 되고 3~4번 과정을 똑같이 거치게 되며 {1, 4}가 추가 된다.

 

6. 이렇게 4까지 돌았으면 1의 for문으로 나오게되는데, 마찬가지로 current.remove(current.size() - 1)에 의해 current가 빈 배열이 된다.

 

이러한 로직으로 순차적으로 더했다 뺐다 하는 과정을 반복하며 부분집합을 완성시킬 수 있다.

 

시간복잡도 - O(n! / k!(n−k)!) ​ (k가 n/2에 가까울수록 높음)

공간복잡도 - O(k * nCr)

 

정리

재귀를 이용한 조합 구현