순열 구하기(중복X)

문제

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

제한사항

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

입출력 예

풀이

function solution(m, arr) {
  let answer = [];
  let n = arr.length;
  let tmp = new Array(m).fill(0);
  let check = new Array(n).fill(0); //arr 배열이랑 같은 크기

  function dfs(L) {
    if (L === m) {
      answer.push([...tmp]);
    } else {
      for (let i = 0; i < n; i++) {
        if (!check[i]) {
          check[i] = 1;
          tmp[L] = arr[i];
          dfs(L + 1);
          check[i] = 0;
        }
      }
    }
  }
  dfs(0);
  return answer;
}

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

• 중복순열 구하기에서 check 배열로 check하고 해제하는 테크닉만 추가된 문제이다.

function solution(m, arr) {
  let answer = [];
  let n = arr.length;
  let tmp = [];
  let check = new Array(n).fill(0); //arr 배열이랑 같은 크기

  function dfs(L) {
    if (m === tmp.length) {
      answer.push([...tmp]);
    } else {
      for (let i = 0; i < n; i++) {
        if (!check[i]) {
          check[i] = 1;
          tmp.push(arr[i]);
          dfs(L + 1);
          check[i] = 0;
          tmp.pop();
        }
      }
    }
  }
  dfs(0);
  return answer;
}

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