[Medium] 77. Combinations

문제

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

 

풀이 과정

Example 1를 예시로 설명하겠다.

• start = 1, curComb = [] 를 인자로 보내는 comb를 실행한다.
• (2)번의 for문을 돈다.
  • start = 2, curComb [1] 를 인자로 보내는 comb를 재귀 호출한다.
• 또 (2)번의 for문을 돈다.
  • start = 3, curComb = [1, 2] 를 인자로 보내는 comb를 재귀호출한다.
• 이 때, 길이가 2 === k 에 조건을 충족하기 때문에 (1)번 코드가 실행된다.
  • curComb = [1, 2] 를 result.push() 한다. 
  • return을 하게 되면 재귀 함수가 반환된다.
• 그 전에 호출했던 (2)번에서 i = 2, curComb = [1, 2]로 돌아오게 된다.
  • curComb.pop()을 통해, curComb = [1]이 된다. 
• for문을 마치고, (2)의 두번째 loop를 시작한다. 이때 i++ 되므로 i = 3이 된다. 
  • curComb.push를 통해 curComb = [ 1, 3 ] 이 된다.
  • comb() 재귀 호출을 통해 result 값에 들어가게 된다. 반환되어 (2)로 돌아온다.
  • curComb.pop()를 통해 curComb = [ 1 ] 이 된다.
• for문을 마치고, (2)의 세번째 loop를 시작한다. 이때 i++ 되므로 i= 4이 된다. 
  • curComb.push를 통해 curComb = [ 1, 4 ] 이 된다.
  • comb() 재귀 호출을 통해 result 값에 들어가게 된다. 반환되어 (2)로 돌아온다.
  • curComb.pop()를 통해 curComb = [ 1 ] 이 된다.
• for문을 마치고 return 된다. 이때, (2)의 i = 1, curComb [ 1 ] 으로 돌아온다.
  • curComb.pop()이 되어 curComb = [] 이 된다.
• for문을 두번째 돈다. 
  • 이때 curComb.push를 통해 curComb [ 2 ] 가 된다. 
• ... 이러한 과정을 연속적으로 하게 된다. 

 

풀이 코드

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {    
    let result = [];
    
    //---------------------------
    let comb = (start, curComb) => {
        // k 길이가 되면 result에 넣는다. -- (1)
        if(curComb.length === k){
            result.push([...curComb]);
            return;
        }
        
        // curComb에 값을 넣는다. -- (2)
        for(let i = start ; i <= n ; i++){
            curComb.push(i)
            comb(i + 1, curComb);
            curComb.pop();
        }
        return;
        
    }
    
    //---------------------------
    
    comb(start = 1, curComb = []);
    return result;
};