Giả sử chúng ta có một số nguyên dương n. Chúng ta phải tìm tất cả các tổ hợp của các số nguyên dương mà cộng lại bằng số đó. Ở đây chúng ta chỉ muốn các tổ hợp, không phải các hoán vị. Với giá trị n = 4, sẽ có [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4].
Chúng ta sẽ giải quyết bài toán này bằng đệ quy. Chúng ta có một mảng để lưu trữ các tổ hợp, và chúng ta sẽ điền mảng đó bằng phương pháp đệ quy. Mỗi tổ hợp sẽ được lưu trữ theo thứ tự tăng dần của các phần tử.
Ví dụ
#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); }
Kết quả
1 1 1 1 1 1 2 1 3 2 2 4