BOJ - Skill) n개 중 m개 택 모든 조합 출력 알고리즘

  '알고리즘 문제 해결 전략 세트'의 Brute-Force 소개란에서 제시하고 있는 아래의 소스 코드는 재귀호출을 이용해 'n개의 원소 중 m개를 택하는 모든 조합을 출력하는' recursive한 알고리즘을 보여주고 있다.

 매우 손쉬운 코드이고, 익숙한 코드이지만, 그럼에도 불구하고 매우 중요한 Insight를 제공하는 코드라고 느껴지기 때문에 Velog에 따로 정리해두고자 한다.

void pick(int n, vector<int>& picked, int toPick) {
    if (toPick == 0) {
    	// picked 배열 출력
        return;
    }
    
    int smallest = picked.empty() ? 0 : picked.back() + 1;
    
    for (int next = smallest; next < n; next++) {
    	picked.push_back(next);
        pick(n, picked, toPick - 1);	// toPick은 앞으로 더 고를 원소의 수
        picked.pop_back();
    }
}

  toPick, 즉, 더 고를 원소의 수가 0, 즉, 다 골랐을 때 picked 배열을 출력하고, 그 전에는 계속해서 재귀 호출이 일어난다. smallest는 현재 picked 배열의 가장 마지막 원소에서 1을 더한 값을 받는데, 그 이유는, 우리가 조합을 표시하는 루틴이 (0,1,2,3), (0,1,2,4), ~ 이런 패턴을 보이기 때문이다.
  최초 수행된 pick 함수가 종료되면 모든 조합이 출력된 것이다.

  이는, 흔히 초보 프로그래머가 '모든 조합을 출력하라'라는 문제 상황에서 Naive한 반복문의 Dirty한 중첩 형태를 구성하는 실수를 할 때 배우기 좋은 알고리즘이다. 즉, 중첩 반복문으로 모든 조합을 보여주려는 시도보다 훨씬 좋은 브루트포스 알고리즘인 것이다.