2. Комбинаторные объекты

Генерация подмножеств

var a:array[1..20] of integer; { множество заданных значений }
                               { одинаковых элементов нет }
    n:integer; { количество элементов в множестве }
    b:array[1..20] of boolean; { флаг, входит ли a[i] в подмножество }
procedure gen(i:integer);
var j:integer;
begin
  if i>n then { завершение рекурсии }
  begin
    { обработка полученного подмножества, например, печать }
    for j:=1 to n do
      if b[j] then
        write(' ',a[j]);
      writeln;
    exit;
  end;
  b[i]:=false; { i-й элемент не включаем в подмножество }
  gen(i+1); { и рассматриваем все варианты для этого случая }
  b[i]:=true; { i-й элемент включаем в подмножество }
  gen(i+1); { и рассматриваем все варианты для этого случая }
end;

Вызов подпрограммы в основной программе выполняется так:
gen(1);
На каждом уровне рекурсии происходит выбор из двух вариантов, всего уровней `n`. Таким образом генерируется `2^n` различных подмножеств.

Пример применения:
Разбор задачи 592. Головоломка