資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法律學使用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
更新時間： 2019-11-01
408次瀏覽
廣告