C++로 첫 n개의 자연수를 이용해 길이 k의 모든 증가 수열 출력하기

이 문제에서는 두 개의 정수 K와 n이 주어지며, 첫 n개의 자연수를 사용하여 길이가 K인 모든 증가 수열을 출력하는 것이 목표입니다.

증가 수열(increasing sequence)이란 다음 원소의 값이 항상 이전 원소보다 큰 숫자들의 나열을 의미합니다.

예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력: n = 4, K = 2
출력:
1 2
1 3
1 4
2 3
2 4
3 4

접근 방법

이 문제는 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 먼저 현재 수열을 저장할 길이 k의 배열을 하나 생성합니다. 그다음 배열의 각 자리마다 바로 앞의 원소를 확인하고, 그보다 큰 값만 다음 원소로 선택합니다. 이 과정에서 1부터 n까지의 모든 값을 하나씩 차례대로 고정해 가며 재귀적으로 탐색하면, 가능한 모든 증가 수열을 빠짐없이 구할 수 있습니다.

예제 코드

위 로직을 구현한 C++ 프로그램은 다음과 같습니다.

#include<iostream>
using namespace std;
void printSequence(int arr[], int k) {
    for (int i=0; i<k; i++)
       cout<<arr[i]<<" ";
    cout<<endl;
}
void printKLengthSequence(int n, int k, int &len, int arr[]) {
    if (len == k) {
       printSequence(arr, k);
       return;
    }
    int i = (len == 0)? 1 : arr[len-1] + 1;
    len++;
    while (i<=n) {
       arr[len-1] = i;
       printKLengthSequence(n, k, len, arr);
       i++;
    }
    len--;
}
void generateSequence(int n, int k) {
    int arr[k];
    int len = 0;
    printKLengthSequence(n, k, len, arr);
}
int main() {
    int k = 3, n = 4;
    cout<<"첫 "<<n<<"개의 자연수로 생성한 길이 "<<k<<"의 수열 :\n";
    generateSequence(n, k);
    return 0;
}

실행 결과

첫 4개의 자연수로 생성한 길이 3의 수열 −
1 2 3
1 2 4
1 3 4
2 3 4

동작 원리 정리

핵심 변수인 len은 현재까지 채워진 배열의 길이를 추적합니다. len이 k에 도달하면 완성된 수열을 출력하고 재귀 호출을 종료합니다. 각 단계에서 시작 값은 첫 번째 자리일 때는 1, 그 외에는 이전 원소보다 1 큰 값(arr[len-1] + 1)부터 시작하므로, 자연스럽게 증가 조건이 유지됩니다. 한 분기의 탐색이 끝나면 len을 감소시켜 이전 상태로 되돌아가는 백트래킹 방식으로 모든 경우의 수를 탐색합니다.