พิมพ์ลำดับเพิ่มขึ้นความยาว K จากจำนวนธรรมชาติ N ตัวแรกใน C++

ภาพรวมปัญหา

ได้รับ K และ n ต้องพิมพ์ลำดับเพิ่มขึ้น (strictly increasing) ความยาว K ใช้จำนวนธรรมชาติ 1 ถึง n

ตัวอย่าง

Input: n = 4, K = 2
Output: 1 2, 1 3, 1 4, 2 3, 2 4, 3 4

วิธีแก้ปัญหา (Recursion + Backtracking)

1. สร้างอาร์เรย์เก็บลำดับปัจจุบัน
2. แต่ละตำแหน่งเลือกตัวเลขมากกว่าตัวก่อนหน้า
3. ลองทุกค่าจาก 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 << "Sequence of length " << k << " generated using first " << n << " natural numbers:\n";
    generateSequence(n, k);
    return 0;
}

ผลลัพธ์ (Output)

Sequence of length 3 generated using first 4 natural numbers:
1 2 3
1 2 4
1 3 4
2 3 4