[JavaScript/section 8] 14 - 조합 구하기

📌 14 - 조합 구하기

1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 문제이다.

 

M개를 뽑는다고 했으므로 조합을 이용해야 한다. N이 4이고 M이 2인 경우를 생각해보자❗

위 그림과 같이 L1이 정해지면 L2는 L1 + 1부터 N까지 for 문을 돌면서 정해진다.

 

📝 풀이 방법

s는 for문에서 초기값에 해당한다.  다음과 같이 그림으로 한번 이해하고 외우도록 하자(중요❗) 

• L(레벨)이 m과 같다면 하나의 경우가 만들어진 것이므로 tmp를 얕은 복사(slice)하여 answer에 추가한다.

function solution(n, m) {
  let answer = [];
  let tmp = Array.from({ length: m }, () => 0);

  function DFS(L, s) {
    if (L === m) answer.push(tmp.slice());
    else {
      for (let i = s; i <= n; i++) {
        tmp[L] = i;
        DFS(L + 1, i + 1);
      }
    }
  }
  DFS(0, 1);

  return answer;
}

console.log(solution(4, 2));