77. Combinations

77. Combinations

문제

1부터 n까지 k자릿수 숫자 조합 만들기 문제이다. 수열 문제는 처음에 접근하기가 쉽지 않았는데, 여러 문제를 풀면서 공식을 익히니까 조금씩 눈에 들어오는 것 같다.

테스트 케이스

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

풀이

1. 먼저, 모든 수열을 저장할 combinations 배열을 만든다.
2. generateCombinations 함수를 정의한다.
3. 남아있는 수 remaining이 0이 될 때까지 재귀 호출을 반복한다.
4. 남아있는 수 remaining이 0이 되면 combinations에 조합이 담긴 배열 combination을 푸시한다.
5. combinations 배열을 반환한다.

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */


var combine = function(n, k) {
  const combinations = [];

  var generateCombinations = (combination, num, remaining) => {
    if (remaining === 0) {
      combinations.push(combination)
    } else {
      for (let i = num; i <= n; i++) {
        generateCombinations([...combination, i], i + 1, remaining - 1)
        // i가 1, 2, 3, 4일 때 다음과 같이 
        // generateCombinations([ 1 ], 2, 1) -> remaining이 남음 
        // generateCombinations([ 1, 2 ], 3, 0) -> remaining이 0 -> push
        // generateCombinations([ 1, 3 ], 4, 0) -> remaining이 0 -> push
        // generateCombinations([ 1, 4 ], 5, 0) -> remaining이 0 -> push
        // ...
      }
    }
  }

  generateCombinations([], 1, k) 
  return combinations
};

// 1부터 k 까지 담긴 combination 배열 [[1,2],[1,3],[1,4]]
// 2부터 k 까지 담긴 combination 배열 [...[2,3],[2,4]]
// 3부터 k 까지 담긴 combination 배열 [...[3,4]]
// 위 순서대로 combinations 배열에 쌓이게 된다.