[백준_15650] N과 M (2) [ 백트래킹 - 자바스크립트 ]

문제 

 

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

How to Solve ?

 

N과 M(1) 문제는 백트래킹을 통해서, 순열을 만들어 내는거라면 이번에는 < 조합 >  을 만드는 것이 목표이다.

때문에, 이전과는 다르게 백트래킹을 하면서 시작점을 idx의 값으로 설정하여 이전의 값을 호출 하지 않는 방식으로 작동한다.

 

input : [ 1, 2, 3, 4 ] 
output : [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]

 

 

 

 

 

전체 코드

 

function dfs(idx, cnt) {
  if (cnt === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  // 1로 시작한 백트래킹이 끝나면,
  // 2's 시작점 -> 2이 시작점인 백트래킹의 시작점 : 2
  // 3's 시작점 -> 3이 시작점인 백트래킹의 시작점 : 3
  // => 이를 통해서, 중복된 값 사용을 제어
  for (let i = idx; i <= N; i++) {
    if (visited[i]) continue;

    visited[i] = 1;
    output.push(i);
    dfs(i, cnt + 1);
    output.pop();
    visited[i] = 0;
  }
}

let result = "";
const output = [];
const [N, M] = [4, 2];
const nums = Array.from({ length: N }, (v, i) => i + 1);
const visited = Array(N).fill(0);

dfs(1, 0);
console.log(result.trim());