C ++を使用して、指定された数まで加算されるすべての組み合わせを検索します

正の数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