Determining Big O: Find 4 different numbers in array summing up to S

Question

Given an array of numbers arr and a number S, find 4 different numbers in arr that sum up to S.

Write a function that gets arr and S and returns an array with 4 indices of such numbers in arr.

The solution I came up with involves recursively building up combinations of indices while making sure no combinations are counted more than once. I also prune the search tree by making sure the size of the solution set is no more than 4.

#include <iostream>
#include <vector>
using namespace std;

bool find_sol(vector<int> &N, vector<int> &I, int S, int sum){
  if (I.size() == 4)
    if (S == sum)
      return true;
    else
      return false;
  for (int i = 0; i < N.size(); ++i){
    if (I.empty() || I[I.size()-1] < i){
      I.push_back(i);
      if (find_sol(N,I,S,sum+N[i]))
        return true;
      else {
        I.pop_back();
      }
    }
  }
  return false;
}

int main(){
  int S = 23;
  vector<int> numbers = {1,3,5,6,7,8,9};
  vector<int> indices;
  find_sol(numbers,indices,S,0);

  // prints 0, 2, 5, 6
  for (int i = 0; i < indices.size(); ++i)
    cout << indices[i] <<" ";
  cout<<endl;

  return 0;
}

How can I determine the run time of this algorithm? I feel like it is something like O(n choose 4) but am not sure. The solution tells me the optimal run time is O(n^2).

You might want to review what complexity means. There is no `O(4)`. — too honest for this site, Jul 30 '16 at 18:01
O(nC4) is O(n^4), so that's not going to be the answer. The problem can be solved in O(nS) time. Whether that's better or worse than O(n^2) depends on whether `S` is larger or smaller than `n`. For more, see [this question](https://stackoverflow.com/questions/4355955/subset-sum-algorithm). — user3386109, Jul 30 '16 at 19:20

score 2 · Accepted Answer · answered Jul 30 '16 at 19:58

Your solution is indeed O(nC4) = O(n^4), as it finds all possible combinations and checking them out - and for each combination, there is constant of extra work involved.

It can be done in O(n^2) by first populating a hash map (std::unordered_map) where the keys are the summation of all pairs in the array, and the values are pointing to the indices of these values. Populating this map is O(n^2) average case.

Then, iterate all pairs again, and for each pair i,j with sum d, find in the hash map if there is an entry with key S - d.

Caveat: You also need to make sure this entry does not contain an index from i,j. To be able to cope with it your values of the map might actually be a vector of pairs.

As a side note, this problem is known as the subset-sum problem, with a relaxation of having 4 elements exactly that sums to the target (where the classic problem has no limit for it)

Determining Big O: Find 4 different numbers in array summing up to S

1 Answers1