สมมติว่าเรามีจำนวนบวก n เราต้องหาจำนวนบวกทั้งหมดที่รวมกันเป็นจำนวนนั้น ที่นี่เราต้องการแค่ชุดค่าผสม ไม่ใช่พีชคณิต สำหรับค่า n =4 จะมี [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]
เราจะแก้ปัญหานี้โดยใช้การเรียกซ้ำ เรามีอาร์เรย์สำหรับจัดเก็บชุดค่าผสม และเราจะเติมอาร์เรย์นั้นโดยใช้วิธีการแบบเรียกซ้ำ แต่ละชุดจะถูกจัดเก็บในลำดับขององค์ประกอบที่เพิ่มขึ้น
ตัวอย่าง
#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
