"[백트래킹/JS] 순열/조합" 포스트와 이어지는 내용입니다. (클릭시 이동)

💡 중복순열 (nπr)

중복 가능한 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다(순서 상관O)

순열은 중복을 허락하지 않는다!

문제 링크

https://www.acmicpc.net/problem/15649

풀이

순열에서는 중복을 허용하지 않기 위해 자신이 밟은 위치를 체크하는 배열을 생성했지만,
중복 순열에서는 중복을 허용하기 때문에 방문 체크 배열을 만들지 않아도 된다

let n, m;
let ans = [];
let ret = [];

const input = () => {
  [n, m] = getLine().split(' ').map(Number);
};

function permutationWithRepetition(cur) {
  if (ans.length == m) {
    ret.push(ans.join(' '));
    return;
  }

  for (let i = 1; i <= n; ++i) {
    ans.push(i);
    permutationWithRepetition(i);
    ans.pop();
  }
}

const solve = () => {
  permutationWithRepetition(0);
  console.log(ret.join('\n'));
};

const main = () => {
  input();
  solve();
};

💡 중복조합 (nHr)

중복 가능한 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다(순서 상관X)

조합은 중복을 허락하지 않는다!

문제 링크

https://www.acmicpc.net/problem/15652

풀이

조합에서는 중복을 허용하지 않기 때문에 cur+1부터 탐색을 해 주었지만,
중복 조합은 중복을 허용하기 때문에 cur(나 자신)부터 탐색을 해 준다

let n, m;
let ans = [];
let ret = [];

const input = () => {
  [n, m] = getLine().split(' ').map(Number);
};

function combinationWithRepetition(cur) {
  if (ans.length == m) {
    ret.push(ans.join(' '));
    return;
  }

  for (let i = cur; i <= n; ++i) {
    ans.push(i);
    combinationWithRepetition(i);
    ans.pop();
  }
}

const solve = () => {
  combinationWithRepetition(1);
  console.log(ret.join('\n'));
};

const main = () => {
  input();
  solve();
};

main();