$n$개 대상에서 $r$ 개를 뽑아 나열하는 모든 경우의 수들은 재귀적으로 구현할 수 있습니다. 항상 이런 조합론 문제들은 백트래킹, dfs 개념을 적용해서 내부에서 loop를 도는 재귀로 풀었습니다. 다른 사람들 풀이를 보면 경우를 나눠서 재귀함수를 두번 호출하는 경우도 봤는데, 직관적이고 깔끔해서 괜찮아 보였습니다. 다만, 성능 측면에서 어느 방식이 더 좋은지 헷갈려서, 재귀 공부도 할 겸 두 방식을 비교해서 정리해보았습니다.

1. 조합 - 경우의 수

    일단 조합의 경우의 수부터 살펴보겠습니다. 뽑을 것이 없으면 경우가 1가지이고, $n$개에서 $n$개를 뽑아야 하면 이것도 경우가 1가지입니다. 그 외에는, $r$개 중에 하나를 포함시키거나, 포함시키지 않는 경우입니다. 즉, 포함시킨다면 $n-1$개에서 $r-1$개를 뽑는 것이고, 포함시키지 않으면 $r$개를 뽑아야 합니다. 위의 표현은 말로 표현해서 길지만 조합 경우의 수를 직관적으로 설명합니다. 이를 수식으로 나타내면 다음과 같습니다.

재귀로 구현하면 다음과 같습니다.

public int combination(int n, int r) {
  if(n == r || r == 0)  {
    return 1;
  } else {
    return combination(n - 1, r - 1) + combination(n - 1, r);
  }
}

2. 조합

    이제 4개 중에서 2개를 뽑는 경우의 수가 6개임은 위의 combination(4, 2)를 이용해서 확인할 수 있습니다. 그런데, 실제 조합 자체를 뽑아내고 싶다면 combination만으로는 부족합니다. 즉, 6개라는 수가 아니라 (1, 2), (1, 3), (1, 4), ... (3, 4)의 6개 순서쌍이 필요하면 조합을 뽑아줄 다른 함수가 필요합니다. 대부분의 문제는 이렇게 특정 배열로부터 조합을 뽑아내거나, 조합들을 배열에 집어넣는 등 조합으로부터 특정 조작이 따라오게 됩니다.

재귀 구현 - combi1

    조합 경우의 수를 구했을 때와 유사하게, 직관적인 관점에서 재귀를 구현하는 과정입니다. list는 조합을 뽑을 대상 리스트, store는 뽑은 조합을 저장해둘 리스트로 설정했습니다. 그리고 현재까지 뽑은 대상의 수를 d, list에서 뽑을 대상의 위치를 i, 뽑는 대상의 수를 r로 두었습니다. n은 list.size()로 대체했습니다. 사실 d는 필요 없는 매개변수인데, 의미를 명확히 하기 위해 추가했습니다.
    대상의 위치를 list 끝까지 확인해서 뽑거나 안뽑는 경우로 조합 재귀문을 작성합니다. 이는 백트래킹에서 자주 발생하는 패턴인데, 일단 의사결정(decision)이 끝난 것과 아직 남은 것을 구분합니다. 우리가 다룰 조합에서는 store 리스트가 의사결정이 끝난 것이고, list와 i값을 이용해서 아직 의사결정이 남은 것을 표현합니다. 그리고 재귀문은 흔히 Choose - Explore - Unchoose 패턴이라는 방식으로 구성합니다.

// d : 현재 뽑은 대상 수(depth), i : 대상의 위치(index), r : 뽑을 대상의 수
public void combi1(List<Integer> list, List<Integer> store, int d, int i, int r) {
  if (r == 0) {
    store.forEach(x -> System.out.print(x + " "));
    System.out.println();
  } else if (i != list.size()) {
      store.add(list.get(i));   // 뽑는다 (Choose)
      combi1(list, store, d + 1, i + 1, r - 1); // 뽑은 경우 나머지 조합을 구한다(Explore)
      store.remove(d);  // 뽑은걸 뺀다 (Unchoose)
      combi1(list, store, d, i + 1, r); // 안 뽑은 경우 나머지 조합을 구한다
  }
}

    list를 (1,2,3,4,5,6)으로 초기화하고 3개를 뽑아서 함수를 돌려보면, 조합 결과는 (1 2 3) 부터 (4 5 6)까지 20개가 출력됩니다. 카운트 변수를 넣고 매 호출마다 횟수를 세보면 83번이 나옵니다.

속도를 개선한 버전 - combi2

    combi1의 아쉬운 점은 조합을 구해봐야 의미가 없는 상황에도 combi1를 호출한다는 것입니다. 예를 들어, i의 위치가 5인데 하나도 안뽑아서 d가 0인 상황을 생각해보겠습니다. 5, 6을 다 뽑아도 조합이 완성되지 않는데, 호출 가능한 조건이 list의 끝까지 가는 것이니 어쨌든 i가 끝까지 도달하게 됩니다. 조건문을 바꿔서 이를 개선해보겠습니다.

public void combi2(List<Integer> list, List<Integer> store, int d, int i, int r) {
  if (r == 0) {
    store.forEach(x -> System.out.print(x + " "));
    System.out.println();
  } else if (r <= list.size() - i) {  // 개선
      store.add(list.get(i));
      combi2(list, store, d + 1, i + 1, r - 1);
      store.remove(d);
      combi2(list, store, d, i + 1, r);
  }
}

    위에서 언급한 '안 돌아도 되는 조건'을 구체적으로 생각해보겠습니다. 매개변수 r에는 현재 뽑아야 할 대상의 개수가 저장되어 있고, list.size()가 대상의 개수입니다. 그리고 i에는 뽑을 대상의 위치가 저장되어 있으니, r이 list.size()-i 보다 작거나 같으면 됩니다. 마찬가지로 카운트 변수를 주고 횟수를 출력해보면 69번이 나옵니다. combi1 보다 개선되었지만, 아직 호출 횟수가 실제 구해야하는 값보다는 많은 것 같습니다.

더 개선하기 - combi3

    아직 중첩 for loop에 비하면 호출 횟수가 매우 많습니다. 아래는 좀 더 개선한 버전입니다. 이번에 store를 배열로 줬는데, list로 설정하는 것보다 초기 크기를 설정하는데 편하기 때문이었습니다. 또, combi3를 오버로딩해서 실제로는 helper함수가 재귀호출로 돌게 했습니다.

public static void combi3(List<Integer> arr, int r) {
  int[] store = new int[r];
  combinations(arr, store, 0, r);
}

private static void combi3(List<Integer> arr, int[] store, int i, int r) {
  if (r == 0) {
    for (int x : store) System.out.print(x + " ");
    System.out.println();
  }

  for (int j = i; j < arr.size(); j++) {
    store[store.length - r] = arr.get(j);   // choose
    combinations(arr, store, j + 1, r - 1); // 뽑은 경우만 본다.
  }
}

    카운트를 세보면 42로 줄어듭니다. combi3는 재귀 함수 안에서 for loop를 돌립니다. 이는 뽑지 않은 경우를 배제하고 뽑은 경우만을 탐색하여, depth를 늘리지 않고 탐색해야 될 부분의 시작점부터 끝까지 choose - explore - unchoose를 진행한다고 생각할 수 있습니다. 재귀 구현에서 속도를 개선했던 방식과 마찬가지로, 이것도 loop 변수인 j의 반복 범위를 줄여서 호출 횟수를 개선할 수 있습니다.

Descision Tree를 통한 성능 개선의 이유 분석

    차이점이 궁금하여 decision tree를 직접 손으로 그려봤습니다. 직관적인 방식을 따라 뽑지 않은 경우를 탐색(combi2)하면 depth가 깊어지면서 호출 횟수가 많아졌습니다. 반면 뽑은 경우만 탐색(combi3)하면 넓게 호출하는 대신 depth가 얕아졌습니다.
    이를 통해 조합론 관련 로직을 구현할 때, 성능 측면에서 백트래킹을 어떻게 구현하느 것이 더 좋은지 알아봤습니다.