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

Одна полезная идея состоит в том, чтобы понять, что двоичное представление всех чисел от 0 до (2 ^ N) -1 на самом деле является набором битовых масок для возможных комбинаций из N отдельных предметов. Например, для N = 3 (3 элемента) и, следовательно, (2 ^ 3) -1 = 7 :

0: 000 = none
1: 001 = third item
2: 010 = second item
3: 011 = second and third items
4: 100 = first item
5: 101 = first and third items
6: 110 = first and second items
7: 111 = all 3 items

Это позволяет очень легко перебирать все возможные варианты выбора в установленный порядок (так что невозможно пропустить или дважды посетить любой потенциальный выбор).

Есть несколько способов решения этой проблемы. Одно из них - классическое решение DP, опубликованное другими. Я собираюсь опубликовать решение, которое использует только память O (S), где S - это сумма всех целых чисел в массиве (также может быть изменено, чтобы обозначать желаемую сумму), а другое решение использует очень эффективный рандомизированный алгоритм, который может быть протестированным, чтобы быть очень быстрым даже для сотен тысяч чисел любого размера, и даже для рациональных и отрицательных чисел.

Решение DP за время O (нс) и память O (S):

//let F[i] = 1 if we can get sum i and 0 otherwise
F[0] = 1; // we can always make sum 0
for ( int i = 1; i <= n; ++i )
  for ( int j = S; j >= numbers[i]; --j )
    F[j] |= F[j - numbers[i]]; // basically, if F[j - numbers[i]] == 1, then we 
                               // can add numbers[i] to make F[j] 1, otherwise 
                               // we can't. A bitwise or operation will save us 
                               // an if/else structure basically.

Псевдокод для рандомизированного алгоритма: Let Used = список чисел, которые вы суммируете. {{1} } Пусть Unused = список чисел, которые вы НЕ суммируете. Пусть tmpsum = 0. Пусть S = желаемая сумма, которую вы хотите достичь.

for ( each number x you read )
  toss a coin:
    if it's heads and tmpsum < S
      add x to Used
    else
      add x to Unused

while ( tmpsum != S )
  if tmpsum < S 
    MOVE one random number from Unused to Used
  else
    MOVE one random number from Used to Unused

print the Used list, containing the numbers you need to add to get S

Это будет намного быстрее, чем решение динамического программирования, особенно для случайных входных данных. Единственная проблема заключается в том, что вы не можете надежно определить отсутствие решения (вы можете позволить алгоритму работать в течение нескольких секунд, а если он не завершится, предположите, что решения нет), и вы не можете быть уверены, что получите решение. с минимальным количеством выбранных элементов. Опять же, вы можете добавить некоторую логику, чтобы алгоритм продолжал работать и пытался найти решение с меньшим количеством элементов, пока не будут выполнены определенные условия остановки, но это замедлит его работу.Однако, если вас интересует только работающее решение, и у вас МНОГО чисел, а желаемая сумма может быть ОЧЕНЬ большой, это, вероятно, лучше, чем алгоритм DP.

Еще одним преимуществом этого подхода является то, что он также будет работать для отрицательных и рациональных чисел без каких-либо модификаций, что неверно для решения DP, поскольку решение DP включает использование частичных сумм в качестве индексов массива, а индексы могут быть только естественными. числа. Вы, конечно, можете использовать, например, хэш-таблицы, но это сделает решение DP еще медленнее.

Чтобы сгенерировать все комбинации, вы должны искать обратное отслеживание: http://en.wikipedia.org/wiki/Backtracking

Для этой задачи вам нужно использовать что-то вроде этого:

void back(int k)
{
  if ( k > numElements )
  { 
    // add all the nums[i] for which st[i] == 1 and check
    // if their sum is what you desire, then return;
  }

  for ( int i = 0; i <= 1; ++i )
  {
    st[k] = i;
    back(k + 1);
  }
}

Вы должны запустите его на бумаге для небольшого количества элементов, чтобы увидеть, как это работает. Вы можете оптимизировать его, вычисляя сумму по ходу дела, избегая, таким образом, окончательного суммирования. Это общая идея.

Здесь необходимо немного осторожно относиться к терминологии. Комбинации используется для обозначения выбора k элементов из набора n элементов, где порядок k элементов не имеет значения. . Связанная концепция выбора k элементов из набора n элементов, где порядок k элементов имеет значение, упоминается как перестановка .

Однако то, о чем вы вначале говорите:

Учитывая массив целых чисел и сумму, проверьте, складывается ли какая-либо комбинация в сумму. Другое дело

- здесь нет фиксированного k : вас интересует подмножество исходных элементов любого размера.

Набор всех подмножеств набора S называется набором мощности S, и существует очень простая формула для количества элементов, которые он содержит. Я оставлю это как упражнение - как только вы его проработаете, должно быть относительно очевидно, как выполнять перечисление через элементы powerset набора.

(Подсказка: набор степени {1, 2} равен {{}, {1}, {2}, {1, 2}} )

Рекурсивно. Псевдокод будет примерно таким:

function f(set,currentelement,selectedelements,sum,wantedsum)
{
for (thiselement=currentelement+1 to lastelement)
   {
   if (sum+thiselement==wantedsum) print out selectedelements+thiselement;
   if (sum+thiselement<wantedsum)
      {
      f(set,thiselement,selectedelements+thiselement,sum+thiselement,wantedsum);
      }
   }

Я вижу два варианта:

1. Вычислить набор мощности входного массива и проверить сумму каждого элемента в наборе мощности (см. http://en.wikipedia.org/wiki/ Power_set ). Вероятно, это O (2 ^ N) и не подходит для больших N
2. Попробуйте что-нибудь с задачей о рюкзаке 0-1 (см. http://en.wikipedia.org/wiki/Knapsack_problem ). Это должно либо найти наибольшую сумму меньше, чем ваше желаемое значение, сумму, которая является вашим желаемым значением, либо ничего не найти. Основываясь на результатах, вы можете ответить на свой исходный вопрос. 0-1 Рюкзак хорош, потому что он работает за полиномиальное время O (N ^ c), где c - постоянное значение. Я не помню, работает ли это для отрицательных чисел.

Если у вас есть как положительные, так и отрицательные целые числа, вы столкнетесь с комбинаторным взрывом, когда любой выбранный вами алгоритм будет замедляться на фиксированный процент при каждом увеличении длина вашего массива. (Если у вас есть только положительные целые числа, вы можете ограничить свой поиск, как только целевая сумма будет превышена.)

Граничный вопрос: разрешено ли вам повторно использовать целые числа?

Вам следует искать «комбинаторные алгоритмы». Незавершенный фолиант Кнута может вам очень помочь, если вы хотите глубже изучить вопрос.

Это похоже на классическую проблему рекурсии. Вы начинаете с первого элемента и рассматриваете остальную часть массива; для каждого элемента он либо выбран, либо нет. Базовый случай - когда начальный индекс больше длины массива. Что-то вроде

public static bool canSum(int start, int[] array, int sum)
{
      if (start >= array.Length)
           return sum == 0;
      return canSum(start + 1, array, sum - array[start]) || canSum(start + 1, array, sum);
}

Это не ответ на ваш «комбинированный» вопрос, но, вероятно, это оптимальное решение вопроса: P

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

Сумма подмножества имеет псевдополиномиальный алгоритм с использованием динамического программирования:

псевдокод из этой ссылки

Subset-Sum-Solver[S = w1,w2, . . . ,wn,B]
1 Initialize M[0..n, 0..B] everywhere False apart from M[0, 0] = True
2 for i  from 1 to n
  do
3    for w from  0 to B
     do
4        M[i,w] = M[i − 1,w] _M[i − 1,w − wi]
         (any reference outside the array returns false)
5 Output M[n,B]

где B - сумма, S - набор чисел, n - мощность S (количество элементов в S), а M - матрица по B. Этот алгоритм - O (nB)

В случае вопроса на собеседовании проделайте это для каждой суммы, и вы получите алгоритм O (nmB), где m - количество сумм, которые вы должны проверить.

Вопрос несколько двусмысленный: является ли массив целых чисел, используемый для получения подмножеств, одним и тем же массивом сумм? т.е. суммируется ли подмножество целых чисел в массиве A с одним из целых чисел в массиве A? в этом случае алгоритм будет O (n ^ 2B), так как n == m

Если вы все же решите рассчитать набор мощности, это можно легко сделать функционально.

В Haskell есть функции подпоследовательностей, которые, по сути, возвращают набор мощности любого набора в виде списка списков.

Или вы можете написать это самостоятельно

powerSet :: [a] -> [[a]]
powerSet [] = [[]]
powerSet x:xs = map (:x) (powerSet xs) ++ (powerSet xs)