Задачи дискретной математики, к которым относится большинство
олимпиадных задач по информатике, чаще всего сводятся к перебору
различных конфигураций объектов и выбору среди них наилучшего, с точки
зрения условия той или иной задачи. Поэтому знание алгоритмов
генерации наиболее употребительных комбинаторных конфигураций
является необходимым условием успешного решения олимпиадных задач в
целом. С точки зрения информатики, важно также знать количество
различных вариантов для каждого типа комбинаторных конфигураций, так
как это позволяет реально оценить вычислительную трудоемкость
выбранного алгоритма решения той или иной задачи на перебор вариантов
и, соответственно, его приемлимость для интересующей нас размерности
рассматриваемой задачи. Перейдем к рассмотрению трех основных
конфигураций: k-элементные подмножества множества, состоящего из n>k
элементов (или различные сочетания из n элементов по k элементов);
все подмножества данного множества из n элементов; различные
перестановки элементов n-элементного множества.

         1. Генерирование k-элементных подмножеств.
      В комбинаторике количество различных сочетаний из n элементов
                                                   k
по k элементов обозначают C   и выражается оно следующей формулой:
                                                   n
               k      n!       n(n-1)...(n-k+1)
              C = -------- = ----------------
                n   k!(n-k)!          k!
доказательство которой можно прочесть, например, в [1]. Здесь 0<k<n.
                                                                              1    n-1
Заметим, что для фиксированного числа n, C = C    = n, а
                                                                               n    n
максимального значения число сочетаний достигает при k=n/2.
Обычно генерацию всех k-элементных подмножеств проводят в
лексикографическом порядке, тем более, что в данном случае это не
приводит ни к усложнению, ни к увеличению вычислительной трудоемкости
алгоритма. Напомним, что порядок подмножеств называется
лексикографическим, если для любых двух подмножеств справедливо, что
раннее должно быть сгенерировано то из них, из индексов элементов
которого можно составить меньшее k-значное число в n-ричной системе
счисления (или в десятичной, для n<10). Так, для n=6 и k=3 сочетание
из третьего, первого и пятого элемента должно быть сгенерировано
раньше, чем из второго, третьего и четвертого, так как 135<234.
      Рассмотрим сначала рекурсивный алгоритм решения данной задачи.
Идея сведения данной задачи к задаче меньшей размерности следующая:
первым элементом подмножества может быть любой элемент, начиная с
первого и заканчивая n-k+1 -ым элементом. После того, как индекс
первого элемента подмножества зафиксирован, осталось выбрать k-1
элемент из элементов с индексами, большими чем у первого. Мы свели
исходную задачу к задаче меньшей размерности и далее поступаем
аналогично. Когда выбран последний элемент, то мы достигли низшего
уровня рекурсии и выбранное подмножество можно распечатать.
      В предлагаемой ниже программе массив a содержит элементы
исходного множества и может быть заполнен произвольным образом. В
массиве p будем формировать очередное сочетание из k элементов.
Параметры процедуры cnk следующие: m - сколько элементов из множества
нам осталось выбрать, l - начиная с какого элемента исходного
множества следует выбирать эти m элементов.

const n1=20;
type main=array[1..n1] of integer;
var k,n,i,j:integer;
        a,p:main;
procedure cnk(m,l:integer);
var i:integer;
begin
if m=0 then
    begin
       for j:=1 to k do
        write(p[j]:4);
       writeln;
    end
else
      for i:=l to n-m+1 do {цикл по возможным индесам для выбора
                            первого из m элементов}
      begin
        p[k-m+1]:=a[i];
        cnk(m-1,i+1)
      end
end;
begin
readln(n,k);
for i:=1 to n do
    a[i]:=i; {данный массив может быть заполнен произвольно}
cnk(k,1);
end.

      Для того, чтобы построить нерекурсивный алгорим генерирования
всех возможных сочетаний, необходимо и достаточно описать переход от
любого подмножества к следующему за ним в лексикографическом порядке
и условие окончания генерации. Первое подмножество, очевидно, состоит
из первых k элементов исходного множества.
      Пусть b , b , ..., b - индексы элементов некоторого
                  1   2        k
подмножества. Тогда, если b < n, то следующее за ним подмножество
                                                   k
будет состоять из элементов b , b , ...,b   ,b + 1 исходного
                                                    1   2       k-1 k
множества, то есть изменяться будет только индекс последнего
элемента. Если же последний элемент в текущем сочетании уже достиг
границы массива (b = n), то на единицу будет увеличен индекс b   ,
                                   k                                                                             k-1
а последний индекс в сочетании будет равен b   + 2. Когда и
                                                                               k-1
предпоследний индекс исчерпает возможность для увеличения, то
изменяться будет элемент b      и.т.д. Обозначим минимальный из
                                                k-2
измененных, при переходе к текущему сочетанию, элементов q, тогда
следующее сочетание может быть сгенерировано так:

b , b , ..., b    , b + 1, b + 2, ..., b + k - q1 + 1,
1   2        q1-1 q1      q1            q1
где q1=q-1, если последний индекс в предыдущем сочетании равен n
и   q1=k , если последний индекс в предыдущем сочетании меньше n
(то есть изменяется только последний элемент).
      Следующая программа реализует описанный алгоритм. Очевидно, что
условие окончания генерации сочетаний - невозможность увеличения
индекса первого элемента в сочетании, то есть q=1 и b = n. Обратите
                                                                                               k
внимание, что в отличие от предыдущей программы, мы формируем не само
подмножество, а индексы его элементов, поэтому печать самих элементов
(или их обработку согласно условию той или иной задачи) следует
производить с учетом этого факта.

const n1=20;
type main=array[1..n1] of integer;
var k,i,j,n,q:integer;
    a,b:main;
begin
readln(n,k);
for i:=1 to n do
    a[i]:=i;{данный массив может быть заполнен произвольно}
for i:=1 to k do
    b[i]:=i;{массив индексов заполняется однозначно}
q:=k;
while q>=1 do
begin
    for j:=1 to k do
      write(a[b[j]]:4);
    writeln;
    if b[k]=n then q:=q-1
              else q:=k;
    if q>=1 then
      begin
        b[q]:=b[q]+1;
        for i:=q+1 to k do
          b[i]:=b[i-1]+1
      end
end
end.

2. Генерирование всех подмножеств данного множества.
При решении олимпиадных задач чаще всего заранее неизвестно,
сколько именно элементов исходного множества должно входить в искомое
подмножество, то есть необходим перебор всех подмножеств. Однако,
если требуется найти минимальное подмножество, то есть состоящее как
можно из меньшего числа элементов (или максимальное подмножество), то
эффективнее всего организовать перебор так, чтобы сначала проверялись
все подмножества, состоящие из одного элемента, затем из двух, трех и
т. д. элементов. В этом случае, первое же подмножество,
удовлетворяющее условию задачи и будет искомым и дальнейший перебор
следует прекратить. Для реализации такого перебора можно
воспользоваться, например, процедурой cnk, описанной в предыдущем
разделе. Введем в нее еще один параметр: логическую переменную flag,
которая будет обозначать, удовлетворяет текущее сочетание элементов
условию задачи или нет. При получении очередного сочетания вместо его
печати обратимся к процедуре его проверки check, которая и будет
определять значение флага. Тогда начало процедуры cnk следует
переписать так:

procedure cnk(m,l:integer;var flag:boolean);
var i:integer;
begin
if m=0 then
    begin
      check(p,k,flag);
      if flag then exit
    end
else ...

Далее процедура дословно совпадает с предыдущей версией. В
основной же программе единственное обращение к данной процедуре
следует заменить циклом:

k:=0;
flag:=false;
repeat
k:=k+1;
cnk(k,1,flag)
until flag or (k=n);
if flag then
begin
    for i:=1 to k do
      write(p[i]:4);
    writeln;
end
else writeln('no solution');

      Очевидно также, что в основной программе запрос значения
переменной k теперь не производится. Аналогичным образом можно
изменить и нерекурсивную программу перебора всех возможных сочетаний
из n элементов по k элементов.
      Существует также альтернативный подход к перебору всех
подмножеств того или иного множества. Каждое подмножество можно
охарактеризовать, указав относительно каждого элемента исходного
множества, принадлежит оно данному подмножеству или нет. Сделать это
можно, поставив в соответствие каждому элементу множества 0 или 1. То
есть каждому подмножеству соответствует n-значное число в двоичной
системе счисления (строго говоря, так как числа могут начинаться с
произвольного количества нулей, которые значащими цифрами не
считаются, то следует заметить, что в соответствие ставятся n или
менее значные числа). Отсюда следует, что полный перебор всех
подмножеств данного множества соответствует перебору всех чисел в
двоичной системе счисления от ¦00...0¦1   до ¦11...11¦. Последнее из
                              L-------        L--------
                              n-1 нуль        n единиц
таких чисел соответствует всему исходному множеству. Теперь легко
подсчитать и количество различных подмножеств данного множества. Оно
             n                 n
равно 2 - 1 (или 2 , с учетом пустого множества). Таким образом,
сопоставляя два способа перебора всех подмножеств данного множества,
мы получили следующую формулу:

1      2      3          n-1    n   n
C + C + C + ... C    + C = 2 - 1.
n    n      n         n      n

Прежде, чем перейти к рассмотрению программ, соответствующих
второму способу перебора, укажем, когда применение этих программ
целесообразно. Во-первых, данные программы легко использовать, когда
необходимо в любом случае перебрать все подмножества данного
множества (например, требуется найти все решения удовлетворяющие тому
или иному условию), во-вторых, когда с точки зрения условия задачи не
имеет значения, сколько именно элементов должно входить в искомое
подмножество. На примере такой задачи мы и напишем 2 варианта
программы. Задача взята из книги [2].

Условие задачи: дан целочисленный массив A[1..N] и число M. Найти
такое множество элементов A[i1],A[i2],...A[ik] такое,
что 1<=i1<i2<i3<...<ik<=N и A[i1]+A[i2]+...+A[ik]=M.

procedure subsets1;
var k,s:integer; q,j:longint;
begin                                                                      n
q:=1 shl n; {таким образом мы помещаем в q число 2 }
for j:=1 to q-1 do {цикл по всем подмножествам}
    begin s:=0;
      for k:=1 to n do
        if ((j shr (k-1))and 1)=1 {данное условие означает, что в
         k-той справа позиции числа j, в 2-ной системе, стоит 1}
          then s:=s+a[k];
      if s=m then
        begin
          for k:=1 to n do
            if ((j shr (k-1))and 1)=1 then write(a[k]:4);
          writeln; exit
        end
    end
end;

Данная программа обладает одним недостатком: мы не можем с ее помощью
перебирать все подмножества множеств, состоящих их более, чем 30
элементов, что обусловлено максимальным числом битов, отводимых на
представление целых чисел в персональных компьютерах (32 бита). На
самом деле, перебор всех подмножеств у множеств большей размерности
вряд ли возможен за конечное время, отведенное для решения той или
иной задачи. Тем не менее, приведем второй вариант данной программы,
где указанное ограничение снимается. Здесь в массиве b, длина
которого соответствует количеству элементов в исходном множестве,
будет записано двоичное представление текущего числа; логическая
переменная flag становится истинной тогда, когда прибавить 1 к
текущему числу уже невозможно, что означает окончание перебора.

procedure subsets2;
var b:array[1..n] of 0..1;
    flag:boolean; k:integer;
procedure plus1(n:integer);{прибавление 1 в 2-ной системе счисления}
    begin
      if n>1 then
        if b[n]=0 then b[n]=1
        else begin b[n]:=0; plus1(n-1) end
      else flag:=true
    end;
begin
for k:=1 to n do b[k]:=0;
flag:=false;
repeat
    plus1(n);
    s:=0;
    for k:=1 to n do
      if b[k]=1 then s:=s+a[k];
    if s=m then
      begin
        for k:=1 to n do
          if b[k]=1 then write(a[k]);
        writeln; exit;
      end
until flag;
writeln('no solution')
end;

Для полноты изложения приведем также нерекурсивный вариант
процедуры plus1:

procedure plus1(n:integer);
var i:integer;
begin
i:=n;
while (i>0)and(b[i]=1) do
begin b[i]:=0; i:=i-1 end;
if i>0 then b[i]:=1
else flag:=true
end;

Как и в рекурсивной версии, все цифры числа в двоичной системе
счисления здесь пронумерованы слева направо, поэтому рассмотрение
начинается не с первой цифры, а с n-ной, в подпрограмме же subsets1
цифры нумеровались справа налево, что соответствует иному порядку
рассмотрения подмножеств. Данное расхождение с точки зрения
рассматриваемой задачи не является существенным, хотя и может
привести к тому, что найденные решения будут различными. Расхождение
легко устранить, ставя в соответствие последнему элементу массива b
первый элемент массива a, предпоследнему - второй и т. д., или
переписав процедуру plus1, изменяя нумерацию цифр на противоположную.

     3. Генерирование всех перестановок n-элементного множества.
      Количество различных перестановок множества, состоящего из n
элементов равно n!. В этом нетрудно убедиться: на первом месте в
перестановке может стоять любой из n элементов множества, после того,
как мы на первом месте зафиксировали какой-либо элемент, на втором
месте может стоять любой из n-1 оставшегося элемента и т.д. Таким
образом, общее количество вариантов равно n(n-1)(n-2)...3*2*1=n!.
      Перейдем к алгоритмам, реализующим генерацию всех перестановок
в лексикографическом порядке, который наиболее приемлим при решении
олимпиадных задач, так как упрощает применение метода ветвей и
границ, который будет описан ниже. Вначале приведем нерекурсивный
алгоритм решения данной задачи, для чего опишем переход от
произвольной перестановки к следующей за ней в лексикографическом
порядке. Переставлять мы будем только индексы элементов, а по
перестановке индексов легко распечатать или обработать перестановку и
самих элементов множества. Обозначим массив индексов элементов - p.
Первоначально он заполнен числами 1, 2, ..., n, которые в дальнейшем
будут меняться местами. Алгоритм состоит из следующих шагов:
1) Необходимо найти такой элемент в массиве p, который меньше
какого-либо элемента в p, находящегося правее данного (то есть
существует возможность его увеличения), причем необходимо найти
такой элемент с максимальным индексом в массиве p. Нетрудно
убедиться, что для решения данной задачи надо просматривать массив
p с правого конца (тогда первый найденный элемет и будет обладать
максимальным индексом) и искать такую пару соседних элементов в p,
для которой справедливо p[i]<p[i+1]. Действительно, согласно
указанному неравенству, правее p[i] существует по крайней мере один
элемент, больший p[i], а так как такое соотношение между соседними
элементами встретилось впервые, то для уже просмотренных элементов
справедливо:
                p[i+1] > p[i+2] > p[i+3] > ... > p[n],       (*)
то есть правее p[i] нет другого элемента, обладающего искомым
свойством.
2) Найденный элемент p[i] меняется местами с минимальным из элементов,
больших p[i] и находящихся правее него. Заметим, что после такой
замены соотношение (*) остается справедливым.
3) Осталось переставить элементы p[i+1], p[i+2], p[i+3], ..., p[n] в
обратном порядке, то есть поменять местами p[i+1] и p[n], p[i+2] и
p[n-1] и т. д.
На этом генерирование следующей перестановки завершено. Алгоритм
закончит генерацию перестановок, когда на первом его шаге искомая
пара p[i] и p[i+1] не будет найдена, что соответствует следующему
порядку индексов: n, n-1, n-2, ..., 3, 2, 1. Приведенная ниже
программа реализует описанный алгоритм.

Рассмотрим теперь рекурсивный вариант программы генерирования
всех перестановок в лексикографическом порядке, опустив раздел
описания переменных, который сходен с предыдущей программой.
Параметром i процедуры Permutations служит место в массиве p, начиная
с которого должны быть получены все перестановки правой части этого
массива. Идея рекурсии в данном случае следующая: на i-ом месте
должны побывать все элементы массива p с i-го по n-ый и для каждого
из этих элементов должны быть получены все перестановки остальных
элементов, начиная с i+1 - го места в лексикографическом порядке.
После получения последней из перестановок, начиная с i+1 - го места,
порядок элементов должен быть восстановлен (для этого используется
процедура циклического сдвига UnIns).

procedure UnIns(i:integer);
var t,k:integer;
begin
t:=p[i];
for k:=i to n-1 do p[k]:=p[k+1];
p[n]:=t;
end;
procedure Permutations(i:integer);
var j,k:integer;
begin
if i=n then
    begin
      for j:=1 to n do write(a[p[j]],' ');
      writeln
    end
else
    begin
      for j:=i to n-1 do
        begin
          Permutations(i+1);
          k:=p[i]; p[i]:=p[j+1]; p[j+1]:=k
          {меняются местами i-ый и j+1 - ый элементы}
        end;
      Permutations(i+1);
      UnIns(i);
      {элемент, стоящий на i-ом месте, cтановится последним}
    end
end;
begin
readln(n);
for i:=1 to n do p[i]:=i;
a:=p; {массив a может быть заполнен произвольно}
Permutations(1);
end.

   4. Примеры олимпиадных задач, сводящихся к генерированию
      комбинаторных конфигураций.
1) Задача 2 тура олимпиады СНГ, г. Могилев, 1992 год.
   На одном острове Новой Демократии каждый из его жителей
организовал партию, которую сам и возглавил. Отметим, что ко всеобщему
удивлению даже в самой малочисленной партии оказалось не менее двух
человек. К сожалению, финансовые трудности не позволили создать
парламент, куда вошли бы, как предпологалось по Конституции острова,
президенты всех партий.
   Посовещавшись, Островитяне решили, что будет достаточно, если в
парламенте будет хотя бы один член каждой партии.
   Помогите Островитянам организовать такой, как можно более
малочисленный парламент, в котором будут представлены члены всех
партий.
   Исходные данные: каждая партия и, соответственно, ее президент
имеют одинаковый порядковый номер от 1 до N (4<=N<=150). Вам даны
списки всех N партий Острова Новой Демократии. Выведите предлагаемый
Вами парламент в виде списка номеров его членов. Например, для
четырех партий:

      Президенты Члены партий
           1     -   2, 3, 4
           2     -   3
           3     -   1, 4, 2
           4     -   2

Список членов парламента: 2 (состоит из одного члена).

Примечание. Получить список одного, как можно более
малочисленного на ваш взгляд парламента.

Решение: с теоретической точки зрения, данная задача совпадает с
задачей генерации всех подмножеств из множества жителей острова новой
демократии. Причем наиболее подходящим кажется первый подход к
решению данной задачи, связанный с генераций различных сочетаний,
начиная с одного жителя. Для полноты изложения, опишем процедуру
сheck, которую следует применить в данной задаче. Исходные данные
следует записать в массив s:array[1..150] of set of 1..150, заполнив
каждый из n первых элементов этого массива множеством тех партий, в
которых состоит тот или иной житель. Тогда процедура check примет
следующий вид:

procedure check(var p:main;k:integer;var flag boolean);
var i:integer; ss:set of 1..150;
begin
ss:=[];
for i:=1 to k do
ss:=ss+s[p[i]];
flag:=(ss=[1..n])
end;

      Как видно из этой процедуры, использование типа "множество",
позволяет не только упростить данную программу, но и существенно
ускорить ее выполнение, по сравнению с работой с массивами. Однако,
большая размерность данной задачи не позволяет считать приведенное
решение удовлетворительным во всех случаях. Так, для n=100, перебор
всех сочетаний из 4-х и менее жителей приводит к рассмотрению около
4-х миллионов вариантов. Для построения кода, пригодного для решения
данной задачи при любых данных, несколько изменим описание массива s:
s: array[1..150] of record
                      name,number:integer;
                      partys: set of 1..150
                    end;
Здесь поле partys совпадает по смыслу с первоначальным описанием
массива s, поле name cоответствует номеру (то есть фактически имени)
жителя и первоначально данное поле следует заполнить числами от 1 до
n cогласно индексу элемента в массиве записей, и поле number
соответствует количеству элементов во множестве из поля partys, то
есть имеет смысл сразу подсчитать, в каком количестве партий состоит
тот или иной житель. Теперь следует отсортировать массив s по
убыванию значений поля number. Тогда легко подсчитать минимально
возможное количество членов парламента kmin:

kmin:=0; nn:=0;
repeat
kmin:=kmin+1;
nn:=nn+s[kmin].number
until nn>=n;

Отсюда очевидно, что сочетания с меньшим количеством жителей
рассматривать не имеет смысла. Верхнюю оценку для числа членов
парламента подсчитаем, построив приближенное решение данной задачи
следующим образом: во-первых, включим в парламент жителя, состоящего
в максимальном количестве партий, затем исключим эти партии из
остальных множеств и заново найдем в оставшемся массиве элемент с
максимальным значением поля number (уже пересчитанного) и включим его
в парламент, и так далее, до тех пор пока сумма значений
пересчитанных полей number у жителей, включенных в парламент, не
будет равна n. Найденное количество членов парламента и будет kmax.
Теперь, если kmin=kmax, то найденное приближенное решение и будет
искомым. В противном случае, следует рассматривать сочетания из
(kmax-1) элемента, затем из (kmax-2) и т. д. элементов до kmin. Если
для сочетаний из какого-то рассматриваемого количества элементов k,
решение найдено не будет, то это означает, что точным является
решение с количеством членов парламента k+1. Так как массив s
упорядочен, то если решение для того или иного значения k существует,
то скорее всего, оно будет найдено при рассмотрении в
лексикографическом порядке первых же сочетаний по k элементов.
Поэтому временная трудоемкость в переборе возникает только, если
решения c данным значением k не существует (а, как было сказано выше,
такой перебор необходим для доказательства точности решения с
количеством членов парламента k+1). В такой ситуации можно
воспользоваться следующим "ненаучным" приемом: на поиск решения для
каждого k, меньшего, чем kmax отведем фиксированное количество
времени, скажем 2-3 секунды (точнее данное время стоит определить
экспериментальным путем). Если за отведенное время решение не
найдено, то следует подсчитать общее количество сочетаний, которое
необходимо перебрать для данного k, причем это число можно сократить
следующим образом: если существует такой элемент j, в упорядоченном
массиве s, что сумма полей number у элементов j+1, j+2, ..., j+k

                                              k                                              k    k
меньше, чем n, то вместо C , следует подсчитать L = C - C   . Далее,
                                                n                                             n   n-j
при L, меньшем некоторого значения, скажем 100000, перебор следует
провести до конца, не рассматривая заведомо бессмысленные сочетания,
начинающиеся с элементов, больших j, в противном случае, следует
считать полный перебор невозможным и закончить выполнение программы.
В любом случае, мы будем иметь какое-либо решение исходной задачи:
точное или приближенное, то есть, возможно содержащее больше членов
парламента, чем минимально возможно. Однако, на практике такой подход
всегда приводит к точному решению, в силу перебора "с предпочтением",
проводимого для каждого k (невозможность проведения полного перебора
для какого-либо k на практике соответствует отсутствию решения для
данного k).

2) Задача 2-го тура 5-ой Всероссийской олимпиады по информатике,
   г.Троицк, 1993 год.
                   "СТО".
      Дан автобусный билет с номером, состоящим из N цифр. Расставить
между цифрами знаки арифметических операций '+', '-', '*', '/'
(целочисленное деление) и скобки таким образом, чтобы значение
полученного выражения было равно 100. Можно образовывать многозначные
числа из стоящих рядом цифр.
      Выражение должно быть корректным с точки зрения арифметики.
Допустимы лишние скобки, не нарушающие корректности выражения. При
вычислениях используется стандартный приоритет операций, число цифр N
в номере билета не больше 6.

Решение: для построения универсального алгоритма решения данной
задачи будем считать слияние двух соседних цифр одной из операций.
Тогда между каждой парой соседних цифр может стоять одна из 5
                                                          N-1
операций. Для N цифр получаем 5    различных вариантов расстановки
операций. Перебирать все варианты расстановки операций удобнее всего
с помощью рассмотрения всех чисел в 5-ричной системе счисления длиной
N-1, то есть для N=6 от 00000 до 44444 (при этом нулем можно
обозначить операцию слияния цифр, единицей - '+', и т. д.). Цифры
текущего числа храним в массиве длиной N-1 и для перебора всех таких
чисел необходимо написать процедуру прибавления 1 в 5-ричной системе
счисления, аналогично процедуре plus1, приведенной выше для двоичной
системы счисления. Для каждого из вариантов расстановки операций
перейдем от исходного массива из N цифр билета, к массиву из К чисел,
где K=(N-количество операций слияния цифр в рассматриваемом
варианте). Теперь мы должны рассмотреть все перестановки из K-1
арифметической операции в данном варианте. Каждая перестановка
соответствует одному из порядков выполнения арифметических операций.
Так, для 4-х чисел, перестановка номеров операций 3,1,2 означает, что
сначала нужно выполнить арифметическое действие между 3-им и 4-ым
числом, затем между 1-ым и 2-ым и затем оставшееся. Если результат
выполнения действий данного варианта в порядке, соответствующем
текущей перестановке, равен искомому числу 100, то задача решена и
можно перейти к печати результата.
    Строку вывода формируем следующим образом: сначала образуем строку
вывода первой операции, включая в нее числа и знак операции,
соответствующий первому числу перестановки. Для каждого из
использованных чисел указываем, что они вошли в первую строку вывода.
При формировании второй строки, если одно из чисел, стоящее слева или
справа от второго арифметического действия в перестановке, уже попало
в первую строку, то вместо него ставится вся первая строка. Для всех
чисел, вошедших во вторую строку указвается их принадлежность к ней.
Далее поступаем аналогично. K-1-ая строка и будет искомой. Причем
строка для каждого из знаков берется в скобки только если:
1) она соответствует знаку "+" и левее этого знака в выражении стоит
знак "-", "*" или "/", а также, если правее этого знака стоит "*"
или "/".
2) она соответствует знаку "*" и левее этого знака стоит знак "/".
Аналогично выписываются правила для "-" и "/".
В результате в конечной строке лишних скобок не будет. Так в выражении
1+(2+3+4)*(5+6)=100
S1=2+3; S2=(S1+4)=(2+3+4); S3=(5+6); S4=S1*S3=(2+3+4)*(5+6)
Для 6 цифр, в худшем случае, необходимо подсчитать значения 157780
арифметических выражений, что вполне реально.

В заключение, приведем текст программы, решающей данную задачу,
опуская подробное описание уже известной нам процедуры permutations и
процедуру unins, которой она пользуется:

label 1;
var b,a,p:array[1..5] of integer;
    c,d:array[1..6] of integer;
    n,q5,k,i,j,n1,ii:integer;
    flag:boolean;
procedure plus1(n:integer);
begin
if n>0 then
    if b[n]<4 then b[n]:=b[n]+1 else
      begin b[n]:=0; plus1(n-1) end
end;
procedure result(n:integer;var flag:boolean);
{проверяет текущую перестановку, записанную в массиве p, текущих
арифметических операций, записанных в массиве a, над числами массива
d на равенство результата 100, в положительном случае печатает
результат, не используя лишних скобок}
var i,j,k,s:integer; v:array[1..5] of string;
    r:array[1..6] of integer;
    v1,v2:string;
    q,a1,d1:array[1..5] of 1..5;
begin
s:=0;{в s мы будем подсчитывать результат}
q:=p;
a1:=a;
d1:=d;
for j:=1 to n do
   begin
     case a1[q[j]] of
      1:s:=d1[q[j]]+d1[q[j]+1];
      2:s:=d1[q[j]]-d1[q[j]+1];
      3:s:=d1[q[j]]*d1[q[j]+1];
      4:if d1[q[j]+1]<>0 then s:=d1[q[j]] div d1[q[j]+1] else exit;
        {делить на 0 нельзя!!!}
     end;
    {после выполнения любого арифметического действия массивы a1 и d1
    сдвигаются; в массиве d1 левое из участвующий в выполненной
    операции чисел заменяется на результат предыдущих действий;
    соответсвенно произведенному сдвигу в массиве перестановок q на
    единицу уменьшаются позиции еще не выполненных арифметических
    действий, если они стоят правее выполненной операции (q[k]>q[j])}
    for k:=q[j]+1 to n do
      d1[k]:=d1[k+1];
    d1[q[j]]:=s;
    for k:=q[j] to n-1 do
      a1[k]:=a1[k+1];
    for k:=j+1 to n do
      if q[k]>q[j] then q[k]:=q[k]-1;
   end;
if s=100 then
begin
    flag:=true;
    for i:=1 to n+1 do r[i]:=0;
    {массив r для пометки чисел: принадлежат ли они уже
     какой-либо строке вывода}
    for j:=1 to n do
      begin
        str(d[p[j]],v1);   str(d[p[j]+1],v2);
        {формирование левого операнда строки}
        if r[p[j]]=0 then begin v[j]:=v1; r[p[j]]:=j; end
                     else begin v[j]:=v[r[p[j]]];
                            k:=p[j];
                            while (k-1>=1)and(r[k-1]=r[p[j]]) do
                              begin k:=k-1;r[k]:=j end;
                            r[p[j]]:=j;
                          end;
        case a[p[j]] of
         1:v[j]:=v[j]+'+';
         2:v[j]:=v[j]+'-';
         3:v[j]:=v[j]+'*';
         4:v[j]:=v[j]+'/';
        end;
        {формирование правого операнда строки}
        if r[p[j]+1]=0 then begin v[j]:=v[j]+v2; r[p[j]+1]:=j; end
                       else begin v[j]:=v[j]+v[r[p[j]+1]];
                              k:=p[j]+1;
                              while (k+1<=n)and(r[k+1]=r[p[j]+1]) do
                                begin k:=k+1;r[k]:=j end;
                              r[p[j]+1]:=j;
                            end;
         {при необходимости строка заключается в скобки}
        if j<n then
          case a[p[j]] of
           1:if (p[j]>1)and(a[p[j]-1]in[2..4])or
                (p[j]<n)and(a[p[j]+1]in[3,4]) then v[j]:='('+v[j]+')';
           2:if (p[j]>1)or(p[j]<n)and(a[p[j]+1]in[3,4])
               then v[j]:='('+v[j]+')';
           3:if (p[j]>1)and(a[p[j]-1]=4) then v[j]:='('+v[j]+')';
           4:if (p[j]>1)and(a[p[j]-1]in[3,4]) then v[j]:='('+v[j]+')';
          end;
      end;
    writeln(v[n]+'=100');
end;
end;
procedure permutations(i,n:integer);
var j,k:integer;
begin
if i=n then
    begin
      result(n,flag);
      if flag then exit
    end
else ...
{далее процедура дословно совпадает с приведенной в пункте 3,
   только при рекурсивном вызове добавляется второй параметр n}
end;
{основная программа}
begin
write('Enter number of the digits:');
readln(n1);
for i:=1 to n1 do
    read(c[i]); {c - массив цифр}
readln;
n:=n1-1;{n - количество операций, включая слияние}
q5:=1;
{q5 - количество вариантов расстановки операций}
for i:=1 to n do
    q5:=q5*5;
flag:=false;
for k:=1 to n do b[k]:=0;
q5:=q5-1;
{операцию полного слияния цифр исследуем отдельно}
if (n1=3)and(c[1]=1)and(c[2]=0)and(c[3]=0) then
   begin writeln('100=100') ;flag:=true end
   else
    for j:=1 to q5 do
      begin
        plus1(n);
        a:=b; {a- массив арифметических операций}
        for i:=1 to n1 do d[i]:=0;
        k:=1;{k- количество чисел, d - массив чисел}
        for i:=1 to n do
          if a[i]>0 then
           begin d[k]:=d[k]+c[i];k:=k+1 end
           else d[k]:=(d[k]+c[i])*10;
        d[k]:=d[k]+c[n1];
        {сдвигом убираем из массива а операции слияния}
        for i:=1 to n-1 do
          while (a[i]=0)and(i<k) do
           for ii:=i to n-1 do
             a[ii]:=a[ii+1];
        {генерируем и анализируем все перестановки из k-1
         арифметического действия}
        permutations(1,k-1);
        if flag then goto 1;
      end ;
      writeln('no solutions');
   1:
end.

Как видно из приведенной программы, наибольшую сложность при
решении данной задачи составляет анализ каждой из перестановок, тем
не менее, умение правильно и быстро их генерировать позволяет решить
задачу за короткий срок, не отвлекаясь на программирование
технических "мелочей".