algorithmpolynomial-mathsubset-sump-np

How to pick only 4 set of integers from a set in polynomial time algorithm


The whole thing about this polynomial time is confusing to me for example: I want to write a program in a polynomial time algorithm that will just pick only 4 integers that sum to 0 from a set. For instance: Let assume I have the following set of integers {8, 20, 3, -2, 3, 7, 16, -9}. How can I pick only 4 distinct integers that sum to 0 from a set in polynomial time without having needed to check through every possible length other than 4? Note in the program I don’t need to search through any other possible length than 4. My expected solution is {8, 3, -2, -9} = 0. knowing fully well that i only need 4 integers from the set {8, 20, 3, -2, 3, 7, 16, -9}.

Edit: Will I found a polynomial time solution of {8, 3, -2, -9} even if I increase only the length of the original set from 8 to 100 integers while I will still have to pick my 4 elements that sum to 0 but from the set of 100 integers will it still be polynomial fast with respect to the size of the input (i.e the number of bits used to store the input)?


Solution

  • The following algorithm runs in 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;
      }
    }