#algorithm
#алгоритм
Вопрос:
Есть ли способ перечислить подмножества набора S (заданного как массив) размером, равным k таким образом, чтобы это заняло O(n^k) время, где n — количество элементов в наборе. Перечисление с алгоритмами обратного отслеживания, которые я видел, выполнялось во O(2^n) времени, и мне было интересно, есть ли улучшения в этом.
Комментарии:
1. Алгоритмы обратного отслеживания, которые я видел, обычно
O(k n^k)работают до тех пор, пока у них есть логика для раннего отключения, когда вам нужноiбольше элементов, а< iэлементов меньше. В зависимости от того, как они обрабатывают массивы, там может быть еще один факторk.2. Вы можете подсчитать, сколько раз каждое число появляется в массиве, а затем вы можете перечислять подмножества без необходимости проверять наличие дубликатов, если вы делаете это правильно.
3. Алгоритм R на странице 9 этого раздела Knuth: kcats.org/csci/464/doc/knuth/fascicles/fasc3a.pdf