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);
}

출력