หาการจัดหมู่ทั้งหมดที่ผลรวมเท่ากับจำนวนที่กำหนดด้วย C++

สมมติว่าเรามีจำนวนบวก n เราต้องหาการจัดหมู่ (Combinations) ทั้งหมดของจำนวนบวกที่บวกกันแล้วได้จำนวนนั้น เราต้องการเฉพาะการจัดหมู่ ไม่ใช่การเรียงสับเปลี่ยน (Permutations) สำหรับค่า n = 4 จะมี [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]

เราจะแก้ปัญหานี้โดยใช้การทำซ้ำแบบเรียกตัวเอง (Recursion) เรามีอาร์เรย์สำหรับเก็บการจัดหมู่ และเราจะเติมอาร์เรย์นั้นด้วยวิธีการเรียกตัวเอง แต่ละการจัดหมู่จะถูกเก็บในลำดับเพิ่มขึ้นของสมาชิก

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void getCombination(int arr[], int index, int num, int decrement) {
    if (decrement < 0)
        return;
    if (decrement == 0) {
        for (int i = 0; i < index; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    int prev;
    if (index == 0)
        prev = 1;
    else
        prev = arr[index-1];
    for (int k = prev; k <= num; k++) {
        arr[index] = k;
        getCombination(arr, index + 1, num, decrement - k);
    }
}

void findCombinations(int n) {
    int arr[n];
    getCombination(arr, 0, n, n);
}

int main() {
    int n = 4;
    findCombinations(n);
}

ผลลัพธ์

1 1 1 1 1 1 2 1 3 2 2 4