给定一组整数，其中每个整数都与一组相关联，我需要找到总和为给定整数的所有组合。
例如，假设输入是和。这意味着和。所需的组合是：
。
仅对于两个整数和这很容易，但对于一般数字则涉及更多。我实现了一个蛮力算法，它找到所有可能的组合，然后选择具有正确总和的组合，但是当集合增长时，这很快就会变得太慢。
所以我想知道是否有一种快速的算法可以找到这些（如果牺牲一点速度可以更容易实现，则不必是现有最快的）？
我确定这是一个众所周知的问题，但谷歌搜索我找不到任何东西。
从 n 个不同集合中挑选 n 个整数，总和为给定值
计算科学
组合学
2021-12-03 18:40:46
1个回答
我认为这可能是一个有趣的问题，所以我根据我在问题陈述中的评论为它制定了一个解决方案。可以通过以下链接找到代表解决方案的 C++ 类：
可以使用以下示例代码编写 main.cpp 文件：
#include <stdio.h>
#include "CombinatorialSoln.hpp"
int main( int argc, char** argv ){
// Initialize combinatorial problem
CombinatorialSoln soln;
std::vector<int> iset {1, 3, 2, 5, 6, 3};
soln.setIntegerSet(iset);
// Compute combinations
CombinatorialSoln::Combos combos = soln.computeCombinations(-5);
// print results
for(int i = 0; i < combos.size(); i++ ){
combos[i].print();
}
// Print basic results
soln.showStatistics();
// Complete
return 1;
}
其它你可能感兴趣的问题