[DFS][JS]순열 구하기

문제

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

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. 두 번째 줄에
N개의 자연수가 오름차순으로 주어집니다.

▣ 출력설명

첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

풀이

중복이 되면 안되는 것이 핵심 조건이다.
따라서 주어진 숫자들과 동일한 길이의 배열을 만들고, 각각의 숫자를 지나갔는지를 표시해둔다.
각 뎁스마다 주어진 숫자모두를 순회해야 하므로 for문을 사용했지만, 이 때 조건문을 하나 추가하여 해당 숫자를 지나가지 않았을 경우에만 계속해서 뎁스를 들어가도록 한다.

function solution(numbers, pick) {
  let ch = Array.from({length:numbers.length},() => 0);
  let answer = [];
  let count = 0;
  function dfs(level, result) {
    if(level === pick) {
      count++
      answer.push(result)
      console.log(count)
      return;
    } else {
      for(let i = 0; i < numbers.length; i++) {
        if(ch[i] === 0) {
          ch[i] = 1;
          dfs(level + 1, result + numbers[i]);
          ch[i] = 0;
        }
      }
    }

  }
  dfs(0,'')
  console.log([answer, count])
  return [answer, count]
}

solution([3,6,9], 2)

Reference

• 자바스크립트 알고리즘 문제풀이(인프런)