[LeetCode] 77. Combinations - 문제풀이

Description

1부터 n까지의 정수중에서 k개의 조합의 경우의 수를 모두 반환하는 문제입니다.

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

Solution 1. BackTracking

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

public  void backTracking(List<List<Integer>> result, List<Integer> comb, int start, int n, int level) {
    if (level == 0) { //ending case
        result.add(new ArrayList<Integer>(comb));
        return;
    }
    
    for (int i = start; i <= n-level+1; i++) {
        comb.add(i);
        backTracking(result, comb, i+1, n, level-1);
        comb.remove(comb.size() - 1); 
    }
}

DFS와 유사하게 재귀호출을 통해 가능한 루트를 스캔하며 경우의 수를 추가해줍니다.

Reference

Combinations - LeetCode