สมมติว่าเรามีจำนวนบวก 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