[알고리즘/인프런] 순열 구하기

문제 

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

 

풀이

이전 중복 순열과 풀이는 매우 유사하지만 중복을 허용하지 않기 위해 ch 배열이 필요하다.

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

  function DFS(L) {
    if (L === m) {
      let copy = [...picked];
      permutations = [...permutations, copy];
    } else {
      for (let i = 0; i < n; i++) {
        if (!ch[i]) {
          picked[L] = arr[i];
          ch[i] = 1;
          DFS(L + 1);
          ch[i] = 0;
        }
      }
    }
  }

  DFS(0);
  return permutations;
}