Разложить целое на слагаемые

[Tim]

Необходимо для целого вывести все варианты его разложения на слагаемые без повторов. Например для 4: 3+1, 2+1+1, 2+2, 1+1+1+1.

[Naeel Maqsudov]

Известно ли максимальное раскладываемое N?

Если N известно, то можно придумать более оптимальный алгоритм, если нет, то менее оптимальный, но зато более общий.

[Tim]

Нет, задача для общего случая.

[Eugie]

Вот такой алгоритм (на Delphi):

Код: Выделить всё

program NumDecomp;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var arr: array of Integer;
    ArrSize, level, count: Integer;
    s: String;

procedure Print;
var i: Integer;
begin
  s := '';
  for i := 0 to level do begin
    s := s+IntToStr(arr[i]);
    if i < level then
      s := s+'+';
  end;
  WriteLn(s);
end;

// Recoursively finds all possible additive decompositions of N such that
// Min(addend) >= M; if the tryed composition is monotonely increasing,
// prints it to the screen.
procedure Decomp(N, M: Integer);
var i: Integer;
begin
  if N > 0 then begin
    Inc(level);
    for i := M to N do begin
      arr[level] := i;
      Decomp(N-i,i);
    end;
    Dec(level);
  end
  else begin
    Inc(count);
    Print;
  end;
end;

begin
  Write('Enter a number to decompose additively: ');
  ReadLn(s);
  level := -1; count := 0;
  if TryStrToInt(s, ArrSize) then begin
    SetLength(arr, ArrSize);
    Decomp(ArrSize,1);
  end;
  SetLength(arr, 0);
  WriteLn(Format('The number of variants: %d', [count]));
end.

Смысл, надеюсь, понятен: генерим все возможные комбинации _неубывающих_ последовательностей, дающих в сумме заданное число. Можно и без рекурсии, но это пусть кто-нибудь другой попробует