4 sum problem or a+b+c+d=sum

By | May 24, 2014

The 4 Sum 🙂 problem is like this :

Given an array of integers A, find 4 index of 4 numbers a,b,c,d such that they add up to a specific target number s.The number should not be same.
a+b+c+d =s

The problem is somewhat similar to the 3 sum problem and the solution is also somewhat similar.
.

Ex Input : A={4,5,1,2,3} s=11
output :5,1,2,3

We can take different approaches to solve this problem .

The Naive Approach using four for loops trying all possible sums of 4 numbers .The complexity of this solution is O(n^4).You can easily modify the code for 3 sum problem to make it run for this problem. See here

Approach 2:
Here’s a better algorithm to solve 4 sum problem in O(n^2lgn) without The solution requires O(n^2) extra space
If you want to try it before looking at the solution .I’ll give you on hint .

a+b+c+d=s can be rearranged as a+b=s-(c+d)

.
The algorithm requires creating another array TWOSUMS which has the sum of all possible pair of numbers in the array.We also need to store the index of numbers along with the sum to keep track that the numbers are distinct.
Here’s how each entry in the TWOSUMS array will be stored.
class Entry{
int sum;
int indexa;
int indexb;
}

Entry TWOSUMS[];

Algorithm

  • Sort the array TWOSUMS
  • Initiale two pointers head =0 and tail= TWOSUMS.length
  • If TWOSUMS[head]+TWOSUMS[Tail]=s
      check if TWOSUMS[head].indexa ,TWOSUMS[head].indexb,TWOSUMS[tail].indexa,TWOSUMS[tail].indexb all are distinct or not
    • if all are distinct return indexes
    • else continue
  • else if TWOSUMS[head]+TWOSUMS[Tail]>s set tail tail= tail-1
  • else if TWOSUMS[head]+TWOSUMS[Tail]>s set tail head= head+1
  • repeat till head <= tail

Here’s the code :

For more interesting questions see our DS/Algo page

One thought on “4 sum problem or a+b+c+d=sum

  1. 대전오피

    I loved as much as you will receive carried out right
    here. The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command get got an shakiness over that you wish
    be delivering the following. unwell unquestionably come more
    formerly again as exactly the same nearly a lot often inside case you shield this hike.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *