기저 사례와 매개변수를 모두 설계했으니 이제 구현만 남았습니다. 그림 1-3의 재귀 트리를 구현하는 것이 그리 쉬워 보이지 않습니다. 조금만 더 찬찬히 들여다봅시다. 먼저 각 스택 프레임마다 집합 순서가 모두 다르군요. 매개변수로 {1, 2, 3}을 전달받아 가장 먼저 호출되는 스택 프레임에서 그다음으로 호출되는 스택 프레임들을 살펴보면, 집합에 포함되지 않는 가장 첫 번째 숫자가 차례대로 1, 2, 3인 것을 알 수 있습니다. 여기서 순서는 상관없습니다. 다만 집합의 모든 요소가 한 번씩 꼭 포함되어야 한다는 것이 중요합니다. 이를 그림으로 살펴보겠습니다(그림 1-4).

▲ 그림 1-4 permutation 함수 구현

그림 1-4와 같이 집합의 원소를 차례로 첫 번째 원소와 바꾼 후 다음 스택 프레임에 전달하고, 그다음 집합의 첫 번째 요소를 집합에서 제외시킨다면 그림 1-3과 같이 매개변수를 전달할 수 있을 것입니다. 물론 스택 프레임이 자신이 호출한 재귀 함수를 모두 종료하고 호출한 스택 프레임으로 다시 돌아왔다면 그때는 바꾸었던 원소들을 다시 원래대로 돌려놓아야 합니다. 그래야 원소 순서가 겹치지 않고 집합을 매개변수로 한 번만 전달할 수 있습니다. 이제 실제 코드로 구현해 봅시다.