순열 구하기

문제

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

문제풀이

중복을 허락하지 않기 때문에 별도의 체크 배열을 만들어 이전에 참조했던 value일 경우에는 연산을 수행하지 않도록 한다.

 

코드

function solution(m, arr) {
  let answer = [];
  let n = arr.length;
  let tmp = Array.from({length: m}, () => 0);
  let ch = Array.from({length: n}, () => 0);
  
  function DFS(L) {
    if(L === m) {
      answer.push(tmp.slice());
    }
    else {
      for(let i = 0; i < n; i++) {
        if(ch[i] === 0) { //이전에 참조했던 value일 경우에만 해당 연산 실행
          tmp[L] = arr[i];
          ch[i] = 1; //체크
          DFS(L + 1);
          ch[i] = 0; //하나의 간선에서의 탐색이 끝났다면 해당 value의 체크를 풀어줌
        }
      }
    }
  }

  DFS(0);
  return answer;
}

console.log(solution(2, [3, 6, 9]));