生成添加到特定数字的所有唯一数字组合
我正在编写一个程序来尝试解决数学问题。 我需要生成一个唯一的列表，其中包含与另一个数字相加的所有数字。 例如，加起来为5的4个数字的所有unqiue组合是：
5 0 0 0 4 1 0 0 3 2 0 0 3 1 1 0 2 2 1 0 2 1 1 1 这在perl中很容易暴力，但我在C中工作并希望找到更优雅的解决方案。
在perl中，我会在每列中生成每个可能的数字0-N组合，丢弃那些没有加到目标数字的组合，然后对每行中的数字进行排序并删除重复的行。
我整个上午都在尝试用C写这个，但似乎无法找到一个满意的解决方案。 我需要它才能达到最大N约25 。 你们有什么想法吗？
这是我一直在尝试的一种例子（这会产生重复的组合）：
// target is the number each row should sum to. // Don't worry about overflows, I am only using small values for target void example(int target) { int row[4]; for (int a=target; a>=0; a--) { row[0] = a; for (int b=target-a; b>=0; b--) { row[1] = b; for (int c=target-(a+b); c>=0; c--) { row[2] = c; row[3] = target-(a+b+c); printf ("%2d %2d %2d %2d sum: %d\n", row[0],row[1],row[2],row[3], row[0]+row[1]+row[2]+row[3]); } } } }
这称为分区问题 ， 这里和这里讨论了方法。
如果列数是固定的，最简单的方法是让数字不减少。
void example(int target) { for (int a=0;a<=target;a++) for (int b=a;b<=target-a;b++) for (int c=b;c<=target-(a+b);c++) { int d = target-(a+b+c); if(d>=c) printf ("%2d %2d %2d %2d\n",d,c,b,a); } }
对于更一般的情况，递归搜索是首选。 但无论如何，这个问题的瓶颈是输出 ，不计算在内。
请注意，您不希望任何b > a或任何c > b 。 你可以在你的程序中说出来
for (b ...) { if (b > a) continue; /* continue bypasses the following code and * return control to the loop */ /* ... */ }
此外，您不需要任何负面row[3] 。
按排序顺序生成列表，您不必担心删除重复项。
提示：a =（目标… 0），b =（a .. 0），c =（b … 0），d =（c … 0）
如果数字不大于25，则递归解决方案可能没问题。 伪代码：
function get_summand_list(number) { if number == 0: return empty list for first from number downto 1 { combination = [first_number] + get_summand_list(number - first) } return all combinations }
为了有效地解决这个问题（模拟它是一个指数问题的事实），你想以一种非冗余的方式搜索空间，修剪不可能的解决方案，或者不能导致可能的解决方案的部分解决方案，尽快可能。
最简单的方法是使用递归过程执行此操作。 请注意，如上面的海报所述，您始终可以按排序顺序生成列表，以避免生成重复项。 因此，您的选择必须始终大于（或小于）所选的最后一个元素。
此外，要添加到当前总数中的剩余x min元素的总和必须小于目标值。 也就是说，如果你选择了最多20个的数字，你必须选择3个元素，并且你必须使它加起来为25，并且唯一的选择是1,2和3，那么你就不会能够完成列表（它将加起来26），这样你就可以修剪那个解决方案。
那么，在你的递归解决方案中，
-
检查您是否正在寻找可行的解决方案。 如果没有，只需退出该function。
-
如果您已完成列表，并且它会累计到您的目标，请打印列表并退出。
-
对于每个有效的剩余选项，将其附加到当前解决方案，并使用当前解决方案和当前选择列表重新调用函数。 （你必须删除for循环的下一次迭代的那些选择）。
这应该产生它。
我之前已多次编写过这种类型的代码，因此我很容易发布一个解决方案，但我认为这是功课，所以我不打算这样做。 然而，以上是对该解决方案的相当完整的描述。 使其变得简单的技巧是使用递归解决方案 – 非递归解决方案将非常混乱，因为您需要使用堆栈等基本上模拟递归以获得有效的解决方案。