生成所有唯一的数字组合，加起来达到一定数量

本文介绍了生成所有唯一的数字组合，加起来达到一定数量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在编写一个程序来尝试解决数学问题。我需要生成一个唯一的列表，所有的数字，加起来另一个数字。例如，所有4个数字的组合，最多5个是：

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的每个可能的组合，丢弃不加上目标数字的那些，然后对每行中的数字排序并删除重复的行。 p>

我一直在尝试在C写这个，但似乎没有一个令人满意的解决方案。我需要它工作到最大N约25 。你们有什么想法吗？

这是我一直在尝试的一个例子（这产生重复组合）：

// 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] row [3] = target-（a + b + c）; printf（％2d％2d％2d％2d sum：％d\\\，row [0]，row [1]，row [2]，row [3]， row [0] + row [1] + row [2] + row [3]）; } } } }

解决方案

这被称为分区问题和方法在此处，这里和此处。

I am writing a program to try to solve a math problem. I need to generate a unique list of all of the numbers that add up to another number. For example, all of the unqiue combinations of 4 numbers that add up to 5 are:

5 0 0 0 4 1 0 0 3 2 0 0 3 1 1 0 2 2 1 0 2 1 1 1

This is easy to brute force in perl but I am working in C and would like to find a more elegant solution.

In perl I would generate every possible combination of numbers 0-N in each column, discard the ones that don't add up to the target number, then sort the numbers in each row and remove the duplicate rows.

I've been trying all morning to write this in C but can't seem to come up with a satisfactory solution. I need it to work up to a maximum N of about 25. Do you guys have any ideas?

Here is an example of the kind of thing I have been trying (this produces duplicate combinations):

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

解决方案

This is called a partition problem and approaches are discussed here, here and here.