중복 조합 알고리즘

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

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

중복조합은 조합에서 중복을 허용한다는 것 이다.

우리가 알던 조합에서 { 1, 2, 3 } 중에 2개를 뽑는다고 하면 { 1, 2 } , { 1, 3 } , { 2, 3 } 이렇게 총 3개를 구할 수 있었다.

하지만 중복 조합은 중복을 허용하기 때문에 뽑았던 카드를 다시 한번 뽑을 수 있는 것이다.

즉, {1, 1} , { 1, 2 } , {1, 3 } , {2, 2 }, {2, 3}, {3, 3} 이렇게 경우가 나오게 된다.

헷갈리지 말아야 할 것은, 중복조합이라고 해서 { 1, 2 }를 뽑아놓고 다시 { 2, 1 } 을 뽑을 수 있다 라는 의미가 아닌, {1, 1} ,{ 2, 2 } 이런식으로 뽑았던 카드를 또 뽑을 수 있다는 의미이다.

구현 코드

const MAX = 4;

const combinationWithRepetition = () => {
  const arr = [1, 2, 3, 4]; // 조합에 사용되는 배열
  const selected = [];

  dfs(0, 0, arr, selected);
};

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

    return;
  }

  for (let i = idx; i < MAX; i++) {
    selected[cnt] = arr[i]; // Select[Cnt] = Arr[i]는 Cnt번째 뽑은 카드는 Arr[i]를 뜻한다.
    dfs(i, cnt + 1, arr, selected);
  }
};

combinationWithRepetition();