Description:

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

You may return the answer in any order.

Constraints:

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

생각 과정

문제 파악

주어지는 입력은 1부터 시작하는 연속적인 자연수의 배열이다. 이 배열에서 k개의 묶음으로 나타낼 수 있는 숫자의 조합이 몇 개 발생할 수 있는지를 알아내는 문제이다.

일반적인 사고 방식

공식을 이용하여 생각했을 때 조합의 수는 nCr이다.

순차적으로 생각해보면,

• 시작하는 첫 요소를 선택하고 이것과 조합 가능한 다른 요소들을 모두 선택함으로써 조합이 완성된다.
  
  
• 첫 번째 선택한 요소로 생성 가능한 모든 조합이 조합되면, 첫 번째 요소와 다른 다음 요소를 선택한다.
  
  
• 이때 다음 요소로 생성 가능한 모든 조합에서는 해당 요소 이전에 생성된 조합은 생성할 필요 없다.
  이미 현재 요소와 과거 요소가 조합되는 가능한 조합은 모두 생성되었기 때문이다.

코딩으로 다듬기

일반적인 생각을 프로그램처럼 다듬어보자면, 1부터 n까지의 배열을 순회하면서 현재 요소와 조합 가능한 모든 요소를 통해 1개의 조합을 1개의 배열로 만들어야 한다. 마지막에 이 배열들을 반환한다.

순차적으로,

• 현재 조합의 원소 수 < k 확인
  
  
• 조합 배열에 현재 요소 추가
  
  
• 만약, 현재 조합의 원소 수 == k 이면, 반환할 배열에 현재 조합 배열 내용을 추가하고 조합 배열을 초기화
  
  
• 모든 요소를 순회하며 반복

풀이 코드

  const result = [];
  
  										# 같은 실행을 반복해야 하고, 조합 배열에 대해 공유가 일어나야 하기 때문에 전체적인 흐름은 재귀문을 이용한다.
  function combi(first, array) {		# parameter로 조합의 첫 번째 요소와 조합 배열을 전달한다. 
    if (array.length === k) {			# 조합 배열의 원소 수가 k인지 확인하여 반환할 배열에 추가한다.
      result.push([...array]);
      return;
    }
    for (let i = first; i <= n; i++) {	# 모든 요소를 확인하여 조합을 생성한다.
      array.push(i);
      combi(i + 1, array);				# 조합의 첫 번째 요소가 설정되면 그 다음 요소들에 대해 재귀적으로 조합을 생성한다.
      array.pop();						# 조합 배열에서 요소를 하나씩 제거하여 현재 요소와 다른 모든 요소에 대한 조합을 생성 가능하게 공간을 설정한다. 
    }
    return;
  }

  combi(first = 1, array = []);
  return result;
};