使用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