algorithm - 获取给定数字的所有可能组合以达到给定总和

Question

我有5个数字1，2，3，4和5，我想获取这些数字的所有可能组合，以得出给定的10总数。
例子:

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + = 10
1 + 2 + 2 + 3 + 2 = 10
7 + 3 = 10
4 + 5 + 1 = 10
2 + 2 + 2 + 1 + 3 = 10
and so on...

如果有人可以就如何解决这个问题提供很好的解决方案，我将不胜感激。

Answer 1

另一种方法是转换为线性方程，其中A，B，C，D和E为1,2,3,4或5的数目。

A + B*2 + C*3 + D*4 + E*5 = 10

确定每个变量的范围。

A = (0..10)   // can be 0 to 10 1's
B = (0..5)    // can be 0 to 5 2's
C = (0..3)    // etc
D = (0..2)
E = (0..2)

尝试所有组合。要检查的总组合:11 * 6 * 4 * 3 * 3 = 2,376。

  for var A : integer := 0 to 10 do
    for var B : integer := 0 to 5 do
      for var C : integer := 0 to 3 do
        for var D : integer := 0 to 2 do
          for var E : integer := 0 to 2 do
            if A * 1 + B * 2 + C * 3 + D * 4 + E * 5 = 10 then
            begin
              // output a solution
            end;

完整源解决方案

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.StrUtils;

begin
  for var A : integer := 0 to 10 do
    for var B : integer := 0 to 5 do
      for var C : integer := 0 to 3 do
        for var D : integer := 0 to 2 do
          for var E : integer := 0 to 2 do
            if A * 1 + B * 2 + C * 3 + D * 4 + E * 5 = 10 then
            begin
              Var AResult : string := '';
              for Var I :integer := 1 to E do AResult := AResult + ' + 5';
              for Var I :integer := 1 to D do AResult := AResult + ' + 4';
              for Var I :integer := 1 to C do AResult := AResult + ' + 3';
              for Var I :integer := 1 to B do AResult := AResult + ' + 2';
              for Var I :integer := 1 to A do AResult := AResult + ' + 1';
              writeln(RightStr( AResult,length(AResult) -3) + ' = 10');
            end;
  readln;
end.