数据结构
网络
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次浏览
广告