Как выбрать только 4 набора целых чисел из набора в алгоритме полиномиального времени

Question

Например, все, что связано с этим полиномиальным временем, сбивает меня с толку: я хочу написать программу с алгоритмом полиномиального времени, который просто выберет только 4 целых числа, сумма которых равна 0 из набора. Например: предположим, у меня есть следующий набор целых чисел {8, 20, 3, -2, 3, 7, 16, -9}. Как я могу выбрать только 4 различных целых числа, которые суммируются с 0 из набора за полиномиальное время, без необходимости проверять все возможные длины, кроме 4? Заметьте, что в программе мне не нужно искать любую другую возможную длину, кроме 4. Мое ожидаемое решение: {8, 3, -2, -9} = 0. Хорошо зная, что мне нужно только 4 целых числа из множества { 8, 20, 3, -2, 3, 7, 16, -9}.

Изменить: Буду ли я найти решение за полиномиальное время {8, 3, -2, -9}, даже если я увеличу только длину исходного набора с 8 до 100 целых чисел, в то время как мне все еще придется выбирать мои 4 элемента, которые суммируются в 0 но из набора из 100 целых чисел он все еще будет полиномиально быстрым по отношению к размеру входа (т. Е. Числу битов, используемых для хранения ввода)?

Answer 1

Следующий алгоритм работает в O(N^3 * logN).

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using quadruple = std::tuple<int, int, int, int>;

std::vector<quadruple> find(std::vector<int> vec) {
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  std::vector<quadruple> ret;
  for (auto i = 0u; i + 3 < vec.size(); ++i) {
    for (auto j = i + 1; j + 2 < vec.size(); ++j) {
      for (auto k = j + 1; k + 1 < vec.size(); ++k) {
        auto target = 0 - vec[i] - vec[j] - vec[k];
        auto it = std::lower_bound(vec.begin() + k + 1,
            vec.end(),
            target);
        if (it != vec.end() && *it == target) {
          ret.push_back(std::make_tuple(
              vec[i], vec[j], vec[k], target));
        }
      }
    }
  }
  return ret;
}

int main() {
  std::vector<int> input = {8, 20, 3, -2, 3, 7, 16, -9};
  auto output = find(input);
  for (auto& quad : output) {
    std::cout << std::get<0>(quad) << ' '
              << std::get<1>(quad) << ' '
              << std::get<2>(quad) << ' '
              << std::get<3>(quad) << std::endl;
  }
}

Answer 2

Попробуйте все четверки без повторений. Это занимает максимум (N^4-6N³+11N²-6N)/24 Попытки каждая сделана в постоянное время.

8 + 20 + 3 - 2 = 29
8 + 20 + 3 + 3 = 34
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 - 2 + 3 = 29
8 + 20 - 2 + 7 = 33
8 + 20 - 2 + 16 = 42
8 + 20 - 2 - 9 = 17
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 + 7 + 16 = 51
8 + 20 + 7 - 9 = 26
8 + 20 + 16 - 9 = 35
8 + 3 - 2 + 3 = 12
8 + 3 - 2 + 7 = 16
8 + 3 - 2 + 16 = 25
8 + 3 - 2 - 9 = 0    <==
8 + 3 + 3 + 7 = 21
8 + 3 + 3 + 16 = 30
8 + 3 + 3 - 9 = 5
8 + 3 + 7 + 16 = 34
8 + 3 + 7 - 9 = 9
8 + 3 + 16 - 9 = 18
8 - 2 + 3 + 7 = 16
8 - 2 + 3 + 16 = 25
8 - 2 + 3 - 9 = 0    <==
8 - 2 + 7 + 16 = 29
8 - 2 + 7 - 9 = 4
8 - 2 + 16 - 9 = 13
8 + 3 + 7 + 16 = 34
8 + 3 + 7 - 9 = 9
8 + 3 + 16 - 9 = 18
8 + 7 + 16 - 9 = 22
20 + 3 - 2 + 3 = 24
20 + 3 - 2 + 7 = 28
20 + 3 - 2 + 16 = 37
20 + 3 - 2 - 9 = 12
20 + 3 + 3 + 7 = 33
20 + 3 + 3 + 16 = 42
20 + 3 + 3 - 9 = 17
20 + 3 + 7 + 16 = 46
20 + 3 + 7 - 9 = 21
20 + 3 + 16 - 9 = 30
20 - 2 + 3 + 7 = 28
20 - 2 + 3 + 16 = 37
20 - 2 + 3 - 9 = 12
20 - 2 + 7 + 16 = 41
20 - 2 + 7 - 9 = 16
20 - 2 + 16 - 9 = 25
20 + 3 + 7 + 16 = 46
20 + 3 + 7 - 9 = 21
20 + 3 + 16 - 9 = 30
20 + 7 + 16 - 9 = 34
3 - 2 + 3 + 7 = 11
3 - 2 + 3 + 16 = 20
3 - 2 + 3 - 9 = -5
3 - 2 + 7 + 16 = 24
3 - 2 + 7 - 9 = -1
3 - 2 + 16 - 9 = 8
3 + 3 + 7 + 16 = 29
3 + 3 + 7 - 9 = 4
3 + 3 + 16 - 9 = 13
3 + 7 + 16 - 9 = 17
- 2 + 3 + 7 + 16 = 24
- 2 + 3 + 7 - 9 = -1
- 2 + 3 + 16 - 9 = 8
- 2 + 7 + 16 - 9 = 12
3 + 7 + 16 - 9 = 17

---

Обновление:

По требованию ОП останавливается, когда решение найдено.

8 + 20 + 3 - 2 = 29
8 + 20 + 3 + 3 = 34
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 - 2 + 3 = 29
8 + 20 - 2 + 7 = 33
8 + 20 - 2 + 16 = 42
8 + 20 - 2 - 9 = 17
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 + 7 + 16 = 51
8 + 20 + 7 - 9 = 26
8 + 20 + 16 - 9 = 35
8 + 3 - 2 + 3 = 12
8 + 3 - 2 + 7 = 16
8 + 3 - 2 + 16 = 25
8 + 3 - 2 - 9 = 0    <==