중복 순열 알고리즘

이 글에서는 중복 순열을 재귀를 통해서 구현하는 방법에 대해서 알아보자.

순열은 순서에 상관이 있고 중복을 허용하지 않고 나올 수 있는 모든 수열을 순열이라고 하였다.

중복순열은 말그대로 순열에서 중복을 허용한다는 것이다.

즉, { 1, 2, 3 } 에서 2개를 뽑을 때 일반순열의 경우 { 1, 2 } , { 1, 3 } , { 2, 1 } , { 2, 3 }, { 3, 1 }, { 3 , 2 } 를 출력할 수 있다.

하지만 중복순열의 경우, 뽑았던 카드를 또 뽑아도 되는 중복이 허용되기 때문에 결과가 { 1, 1 } , { 1, 2 }, { 1, 3 }, { 2, 1 } , { 2, 2 } ... 이런식으로 진행된다.

구현 코드

const MAX = 3;

const permutationWithRepetition = () => {
  const arr = [1, 2, 3];
  const selected = [];

  dfs(0, arr, selected);
};

const dfs = (cnt, arr, selected) => {
  if (cnt === 3) {
    console.log(selected.join(" "));

    return;
  }

  for (let i = 0; i < MAX; i++) {
    selected[cnt] = arr[i];
    dfs(cnt + 1, arr, selected);
  }
};

permutationWithRepetition();