알고리즘 [조합] 편

알고리즘 [조합]편

조합이란?

조합(Combinations)은 서로 다른 n개의 원소 중에서 r개를 선택하는 것 방법이다.
조합에서는 선택된 원소의 순서가 중요하지 않다.
즉, 선택된 원소들의 순서를 바꾸어도 같은 조합으로 간주한다

[1,2,3]에서 2개를 뽑아서 조합을 구성한다면
[1,2],[1,3],[2,3]이 나온다.

즉, [1,2]와 [2,1]은 같은 것으로 판단한다.

n개의 원소 중에서 r개를 선택하는 경우의 수라고 생각하면 된다.

조합 구하는 코드

function combinations(arr, k) {
  const results = [];
  function dfs(elements, start, k) {
    if (k === 0) {
      results.push(elements.slice());
      return;
    }
    for (let i = start; i < arr.length; i++) {
      elements.push(arr[i]);
      dfs(elements, i + 1, k - 1);
      elements.pop();
    }
  }
  dfs([], 0, k);
  return results;
}

위 코드는 arr 배열에서 k개를 선택한 모든 조합을 구하는 함수입니다. dfs 함수는 깊이 우선 탐색(dfs) 알고리즘을 이용해 모든 가능한 조합을 탐색합니다. start 인덱스를 이용해 중복된 조합을 제거합니다.