중복 조합 알고리즘
이 글에서는 중복 조합을 재귀를 통해서 구현하는 방법에 대해서 알아보자.
조합은 순서에 상관없이 중복을 허용하지 않고 나올 수 있는 모든 수열을 조합이라고 하였다.
중복조합은 조합에서 중복을 허용한다는 것 이다.
우리가 알던 조합에서 { 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();
Author And Source
이 문제에 관하여(중복 조합 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@codenmh0822/중복-조합-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)