我问一个算法问题，很急

Question

有26个整数，知道他们其中几个的和为x，找出所有的相加和为
x的所有可能的组合。
大家帮忙了

Answer 1

用一种排序法将26个整数存放到数组里：Nm:array[0..25] of integer（从小到大）就一个数的时候，很简单
for i := 0 to 25 do
begin
  if Nm[i] = X then
  begin
    ShowMessage('发现一种可能:' + IntToStr(Nm[i]));
    Break;
  end;
end;下面来判断2个数相加等于X的情况：
if Nm[0] >= X then Exit
else
begin
  if Nm[0] < (X - Nm[0]) then Exit  //不符合2个相加的条件
  else
  begin
    for i := 0 to 25 do
    begin
      if Nm[i] < X then Exit
      else
      for j := 0 to 25 do
      begin
        if Nm[j] = (X - Nm[i]) then
          ShowMessage('发现一种可能:' + IntToStr(Nm[i]) +  '+' + IntToStr(Nm[j]));
      end;  
    end;
  end;
end;现在来讨论大于2个数相加的情况：
建立在判断2个数相加可能性的基础上，如下：...
if Nm[j] = (X - Nm[i]) then
begin
  //当你找到一种2个数相加的可能性的时候
  ShowMessage('发现一种可能:' + IntToStr(Nm[i]) +  '+' + IntToStr(Nm[j]));
  //要找到3个数相加（先从3开始）的可能，在找到上面这种可能的情况下
  //这时问题可以转化为如下2个子问题：
  //(1)求在数组Nm里除了元素Nm[i]以外2个数相加和=（X - Nm[i])的可能性;
  //(2)求在数组Nm里除了元素Nm[j]以外2个数相加和=（X - Nm[j])的可能性;
  //这样问题又归结为求2个数相加的可能性了，算法可以套用求2个数相加时的算法，^_^
  ...
  //以此类推，当你找到一种3个数相加的可能性的时候
  ShowMessage('发现一种可能:' + IntToStr(Nm[i]) + '+' + IntToStr(Nm[j] + '+' + IntToStr(Nm[r])));
  //这时要找4个数相加的可能，在找到上面这种可能的情况下
  //这时问题可以转化为如下3个子问题
  //(1)求在数组Nm里面除了元素Nm[i],Nm[j]以外2个数相加和=(X - Nm[i] - Nm[j])的可能;
  //(2)求在数组Nm里面除了元素Nm[i],Nm[r]以外2个数相加和=(X - Nm[i] - Nm[r])的可能;
  //(3)求在数组Nm里面除了元素Nm[j],Nm[r]以外2个数相加和=(X - Nm[j] - Nm[r])的可能;
  //呵呵,这样问题又归结为求2个数相加的可能性了，算法可以套用求2个数相加时的算法.
  ...
  //以此类推,思想是最终将问题转化为以知和求2个数相加的可能性
   
end;
...

Answer 2

组合可能不全unit Unit1;interface
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Edit1: TEdit;
    procedure FormCreate(Sender: TObject);
    procedure Sum(a: array of Integer; x: Integer);
    procedure Button1Click(Sender: TObject);
    function knap(S, n: Integer): Integer;
  private
    { Private declarations }
  public
    { Public declarations }
  end;var
  Form1: TForm1;
  a: array [0..25] of Integer;
implementation{$R *.dfm}procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
begin
  for i := 0 to 25 do
  begin
    Randomize();
    a[i] := Abs(Random(50));
  end;
end;procedure TForm1.Sum(a: array of Integer; x: Integer);
var
  i,j,temp: Integer;
begin
  for i := 0 to 25 do
    if ( knap(50,i) > 0 )then Memo1.Lines.Add( 'OK')
      else continue;end;procedure TForm1.Button1Click(Sender: TObject);
var
  i,j,temp: Integer;
begin
  for i := Low(a) to High(a) -1 do
    for j:= i+1 to High(a) do
    begin
      if a[i] > a[j] then
      begin
        temp := a[i];
        a[i] := a[j];
        a[j] := temp;
      end;
    end;
  Sum(a, 50);
end;function TForm1.knap(S, n: Integer): Integer;
begin
  if(S = 0) then
  begin
    result := 1;
    exit;
  end;  if ( (s< 0)or ( (s>0) and (n < 1) )) then
  begin
    result := 0;
    exit;
  end;  if (knap(s-a[n], n-1) > 0) then
  begin
    Memo1.Lines.Add(IntToStr(a[n]));
    result := 1;
    exit;
  end;
  Result := knap(s,n-1);
end;end.

Answer 3

只是想法
没有调试
for i:=0 to 25 do 
for j:=0 to 25 do
if a[random(i)]+b[random(j)]=x and i<>j then
begin
 messagedlg('find',mtconfirmation,[mbyes],0);end;

Answer 4

meiqingsong(阿飛) 
好像不对,根本就出不来
luke5678(奇异) 
思路很好,可惜我....

Answer 5

查看一下背包算法，很相似的。
首先由小到大排序，
对于每一种符合的结果，用一个BOOL[26]记录先从第一个数算起，当和大于x时回退，此轮要保证BOOL[1]=TRUE，找到后存结果
然后从第二个数。

Answer 6

然后从第二个数算时，保证BOOL[1]=FALSE，BOOL[1]=TRUE

Answer 7

procedure Question（i,len,sum:integer）;
begin
 if(len=0) then 
  exit;
 case sum-data[i] of
 0: 
   begin
    bool[i]:=true; 
    save();
    question(i+1,len-1,sum-data[i]);
    bool[i]:=false;
    question(i+1,len-1,sum);
    exit;
   end;
 >0;
   begin
    bool[i]:=true;
    question(i+1,len-1,sum-data[i]);
    exit;
   end;
 <0: 
  begin;
    bool[i]:=false;
    question(i+1,len-1,sum);
    exit;
  end;
end;以上只是大体意思，你改一下，作个排序和save（）

Answer 8

const
  cElementCount = 26; //列表数
  cElementEnd = 40; //目标数const
  cElementList: array['a'..'z'] of Integer =
(
01, 02, 03, 04, 05, 06, 07, 08, 09, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
20, 21, 22, 23, 24, 26
);function Combination(mStrings: TStrings; mStr: string;
  mEnd: Integer): Boolean;
  procedure fCombination(mLeft, mRight: string; mSum: Integer);
  var
    I: Integer;
    S: string;
  begin
    if mSum >= cElementEnd then
    begin
      if mSum = cElementEnd then
      begin
        S := '';
        for I := 1 to Length(mLeft) do
          S := Format('%s+%d', [S, cElementList[mLeft[I]]]);
        Delete(S, 1, 1);
        mStrings.Add(Format('%s=%d', [S, cElementEnd]));
      end;
      Exit;
    end;
    for I := 1 to Length(mRight) do
      fCombination(
        mLeft + Copy(mRight, I, 1),
        Copy(mRight, I + 1, MaxInt),
        cElementList[mRight[I]] + mSum
      );
  end;
begin
  Result := False;
  if not Assigned(mStrings) then Exit;
  mStrings.BeginUpdate;
  try
    mStrings.Clear;
    fCombination('', mStr, 0);
  finally
    mStrings.EndUpdate;
  end;
  Result := True;
end; { Combination }procedure TForm1.Button1Click(Sender: TObject);
begin
  Combination(Memo1.Lines, 'abcdefghijklmnopqrstuvwxyz', 0);
end;

Answer 9

我也写了一个函数。
可是，运行速度非常的慢。
如果要把26个数的所以组合列出来，计算时间已经到了不能忍受的地步。
还需要优化。unit Func;interface
uses SysUtils,Classes;type
  TIntList=record
    aInt:array of Integer;
    iP:Integer;
  end;  TArrayList=array of TIntList;  function GetResult(aInput:array of Integer;X:Integer):string;implementation
  function GetResult(aInput:array of Integer;X:Integer):string;
    procedure MadeArrayList(var aList:TArrayList;aInput:array of Integer;iLen:integer);
    var i,j:integer;
    begin
      SetLength(aList,iLen);
      for i:=0 to iLen-1 do
      begin
        SetLength(aList[i].aInt,Length(aInput)-i);
        FillChar(aList[i].aInt[0],Length(aList[i].aInt),0);
        aList[i].iP:=0;
        for j:=Low(aInput)+i to High(aInput) do
        begin
          aList[i].aInt[aList[i].iP]:=aInput[j];
          Inc(aList[i].iP);
        end;
        aList[i].iP:=0;
      end;
    end;
    procedure ProcessArrayList(aList:TArrayList;X:Integer;var sl:TStringList);
      function IncP(aList:TArrayList):boolean;
      var iContinueAdd:Integer;
          i,j:Integer;
      begin
        Result:=True;
        iContinueAdd:=1;
        for i:=High(aList) downto Low(aList) do
        begin
          aList[i].iP:=aList[i].iP+iContinueAdd;          if aList[i].iP>High(aList[i].aInt) then
          begin
            iContinueAdd:=1;
            if i=0 then
              Result:=False;            for j:=i to High(aList) do
              aList[j].iP:=0;
          end
          else
            iContinueAdd:=0;        end;
      end;
      function ExistsRepeat(aList:array of Integer):Boolean;
      var i,j:Integer;
      begin
        for i:=Low(aList) to High(aList) do
         for j:=Low(aList) to High(aList) do
           if (i<>j) and
             (aList[i]=aList[j]) then
           begin
             Result:=True;
             Exit;
           end;
        Result:=False;
      end;
      procedure Sort(var aInt:array of Integer);
      var i,j,iTemp:Integer;
      begin
        for i:=Low(aInt) to High(aInt) do
          for j:=i+1 to High(aInt) do
            if aInt[j]<aInt[i] then
            begin
              iTemp:=aInt[j];
              aInt[j]:=aInt[i];
              aInt[i]:=iTemp;
            end;
      end;    var i,iSum:Integer;
        aInts:array of Integer;
        str:string;
    begin
      SetLength(aInts,Length(aList));
      repeat
        for i:=Low(aList) to High(aList) do
          aInts[i]:=aList[i].aInt[aList[i].IP];        if not ExistsRepeat(aInts) then
        begin
          iSum:=0;
          for i:=Low(aList) to High(aList) do
          begin
            iSum:=iSum+aInts[i];
          end;          if iSum=X then
          begin
            Sort(aInts);            str:='';            for i:=Low(aInts) to High(aInts) do
            begin
              str:=str+IntToStr(aInts[i])+' ';
            end;            if sl.IndexOf(str)=-1 then
              sl.Add(str);
          end;
        end;
      until not IncP(aList);      aInts:=nil;
    end;
    procedure FreeArrayList(aList:TArrayList);
    var i:Integer;
    begin
      for i:=Low(aList) to High(aList) do
      begin
        aList[i].aInt:=nil
      end;
      aList:=nil;
    end;
  var iLen:Integer;
      aList:TArrayList;
      sl:TStringList;
  begin
    sl:=TStringList.Create;
    for iLen:=1 to 5 do
    begin
      MadeArrayList(aList,aInput,iLen);
      ProcessArrayList(aList,X,sl);
      FreeArrayList(aList);
    end;
    Result:=sl.Text;
    sl.Free;
  end;
end.

Answer 10

倒数第十行应该是：
  for iLen:=1 to Length(aInput) do
意思也就是：
  for iLen:=1 to 26 do因为在 iLen 大于7以后，运行所需时间上已经受不了。 调用例子：
procedure TForm1.Button1Click(Sender: TObject);
var a:array [0..25] of Integer;
    i:integer;
begin
  for i:=Low(a) to High(a) do
    a[i]:=i;  Memo1.Lines.Text:=GetResult(a,15);end;
当X为15，26个数为从0..25时的结果：
15 
0 15 
1 14 
2 13 
3 12 
4 11 
5 10 
6 9 
7 8 
0 1 14 
0 2 13 
0 3 12 
0 4 11 
0 5 10 
0 6 9 
0 7 8 
1 2 12 
1 3 11 
1 4 10 
1 5 9 
1 6 8 
2 3 10 
2 4 9 
2 5 8 
2 6 7 
3 4 8 
3 5 7 
4 5 6 
0 1 2 12 
0 1 3 11 
0 1 4 10 
0 1 5 9 
0 1 6 8 
0 2 3 10 
0 2 4 9 
0 2 5 8 
0 2 6 7 
0 3 4 8 
0 3 5 7 
0 4 5 6 
1 2 3 9 
1 2 4 8 
1 2 5 7 
1 3 4 7 
1 3 5 6 
2 3 4 6 
0 1 2 3 9 
0 1 2 4 8 
0 1 2 5 7 
0 1 3 4 7 
0 1 3 5 6 
0 2 3 4 6 
1 2 3 4 5 

Answer 11

非常感谢。大家，辛苦了，有什么好的Idea,可以开小条,我在另开帖子