LeetCode: 77번 (Combinations) [JAVA]

문제 링크

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

Combinations - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 전체 숫자 풀을 나타내는 n, 그 중 조합에 포함될 숫자의 개수를 알려주는 k를 바탕으로 조합을 생성하는 함수 구현
2. 주어진 n과 k 및 필요한 인수를 넣어 조합을 생성 후 반환

 단순히 조합을 생성하는 함수를 구현하면 되는 문제이다. 다만 문제에서 조합을 만들 때 필요한 숫자 배열들이 주어지는 게 아닌 단순 1~n에 해당하는 숫자 풀에서 조합을 생성하면 되기 때문에, 가볍게 조합 함수를 구현할 수 있다.
 기본적으로는 재귀호출을 바탕으로 함수를 생성하며, 함수의 인자로는 조합들을 담을 List<List<Integer>> result, 조합에 넣을 숫자들을 임시적으로 담아놓을 LinkedList<Integer> temp, 현재 넣을 숫자의 시작을 담은 int now, 현재까지 숫자가 몇 개나 포함됐는지를 표시할 int count, 그리고 주어진 int n과 k를 그대로 담기 위한 인자를 사용한다.
 해당 재귀함수의 기저 조건은 결국 현재 temp에 담긴 숫자의 개수가 k만큼 도달하는 것으로, 이후 현재 temp 속 요소들을 복사해 새로운 List를 만들어 result에 추가하고 탐색을 종료하면 된다. 반대로 탐색 조건은, 현재 주어진 now 부터 n까지 for문을 통해 돌며 이 중 하나의 숫자를 temp에 추가하면서, 다음 탐색을 위해 count +1 의 값과 현재 요소 그 다음인 i + 1을 넣어 탐색을 이어나가면 된다. 해당 탐색이 완료되면 일종의 백트래킹을 위해, 넣었던 요소를 다시 제거해주면 된다.
 그렇게 조합 함수를 구현하고 나면, 단순히 인자로 받은 n과 k를 바탕으로 해당 함수를 호출한 후 결과 List를 반환해주면 된다.

 

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        combinations(result, new LinkedList<>(), 1, 0, n, k);
        return result;
    }

    public void combinations(List<List<Integer>> result, LinkedList<Integer> temp, int now, int count, int n, int k) {
        if (count == k) {//지정한 k만큼 다 채워 넣었으면 결과에 추가
            result.add(new LinkedList<>(temp));
            return;
        }

        for (int i = now; i <= n; i++) {//주어진 숫자부터 n까지 중 하나를 선택해 추가 후 재귀호출
            temp.add(i);
            combinations(result, temp, i + 1, count + 1, n, k);
            temp.removeLast();
        }
    }
}

결과