Press "Enter" to skip to content

Hot to solve a k-sum problem – Four Sum in PHP

Ajk 1

Hello again everyone. It has been quite a while since I last wrote something. Well work and life have been busy lately. Therefore I have not had much time for blogging coding fun. Anyhow, we are going to try to solve Four Sum in PHP today. And in case you were wondering… no it does not have a sexual connotation (oops).

What does four sum mean? Well we need to find four numbers (hence the name four sum) – a, b, c, d in an array such that a+b+c+d=target, where target is a given number. K-sum problems can be quite a pain as usually their brute-force solution will be O(n^k). From this excellent post on StackExchange we can get the following 2 generalized algorithms.

For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether S contains both some number x and its negation −x. The algorithm runs in O(nk/2logn) time.

For odd k: Compute the sorted list S of all sums of (k−1)/2 input elements. For each input element a, check whether S contains both x and a−x, for some number x. (The second step is essentially the O(n2)-time algorithm for 3SUM.) The algorithm runs in O(n(k+1)/2) time.

For more details, see: Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. JACM 2005.

In our case though, to solve our k-sum problem there’s one last constraint. To not repeat the different sets, we’re asked to return unique sets where a<=b<=c<=d. This sounds awfully similar to our other posts How To Find Pairs That Equal To A Specific Sum In An Array or How To Find All Triples Whose Sum Is Less Than A Number In An Array, but this time the problem has different constraints and we will try to solve a k-sum problem (Four Sum) in PHP.

Well let’s get to it then. For this I’ll write the code in PHP, just because, well I am writing more php these days and it will be fun to see myself (and yourself) write in different languages.

Four Sum in PHP – Solution

Let’s give a quick analysis on the runtime complexity. Well in worst case complexity this will run at O(n3)! so we just made an n times shortening to our brute force solution ;D.

From now on you (and me) can say we will ace that interview question on Four Sum in PHP!

Hope you guys enjoyed it… and I’ll see you guys next time ;D.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂