[ 자바스크립트(JavaScript) ] section08 - 14 - 조합 구하기

📍 section08 - 14 - 조합 구하기

1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요

 

// 입력
4 2

// 출력
1 2
1 3
1 4
2 3
2 4
3 4
6

 

조합을 구하는 문제인데, 이전에 배웠던 순열과는 조금 다른 방식으로 풀어야 한다. 중복을 허용하지 않는 순열을 구현할 때 배웠던 것처럼 visited 배열로 재귀가 돌아올 때 visited[i]=0을 해주는 방법으로는 풀 수 없고 대신 반복문의 i값을 조금 다르게 i+1을 계속 넘겨줘야 한다. arr값이 따로 주어져있으면 i는 0부터 시작하는데, 이 문제는 arr이 주어져 있지 않고 현재 인덱스가 값으로 들어가므로 s 인자는 1로 초기화하여 넘긴다.

 

 

728x90

 

let n = 4;
let m = 2;

console.log(solution(n, m));

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

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

  DFS(0, 1);
  return answer;
}

👉🏽 [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]