Tìm tất cả các kết hợp cộng tối đa một số nhất định bằng C ++

Giả sử chúng ta có một số dương n. Chúng ta phải tìm tất cả các kết hợp của các số dương, cộng lại với số đó. Ở đây chúng tôi chỉ muốn kết hợp, không phải hoán vị. Đối với giá trị n =4, sẽ có [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]

Chúng tôi sẽ giải quyết điều này bằng cách sử dụng đệ quy. Chúng tôi có một mảng để lưu trữ các kết hợp và chúng tôi sẽ lấp đầy mảng đó bằng cách sử dụ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);
}

Đầu ra