title: 4sum implementation in Java from leetcode
body: <p>The problem statement from leetcode says:</p>
  
  <blockquote>
    <p>Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.</p>
  </blockquote>
  
  <p>Note:</p>
  
  <pre><code>Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  The solution set must not contain duplicate quadruplets.
  </code></pre>
  
  <p>About this four sum problem, I have 2 questions: </p>
  
  <ol>
  <li>Where I went wrong? The compiled code cannot pass all the tests, but I thought the code should be right since it is only using brute force to solve the problem. </li>
  <li>Is there any efficient way to solve the four sum problem instead of this O(n^4) run-time algorithm? </li>
  </ol>
  
  <hr/>
  
  <pre><code>import java.util.List;
  import java.util.ArrayList;
  import java.util.Collections;
  
  public class FourSumSolution{
      public ArrayList&lt;ArrayList&lt;Integer&gt;&gt; fourSum(int[] num, int target){
          ArrayList&lt;ArrayList&lt;Integer&gt;&gt; aList = new ArrayList&lt;ArrayList&lt;Integer&gt;&gt;();
          int N = num.length;
  
          for(int i=0; i&lt;N; i++)
              for(int j=i+1; j&lt;N; j++)
                  for(int k=j+1; k&lt;N; k++)
                      for(int l=k+1; l&lt;N; l++){
                          int sum = num[i] + num[j] + num[k] + num[l];                        
                          if(sum == target){
                              ArrayList&lt;Integer&gt; tempArray = new ArrayList&lt;Integer&gt;();
                              Collections.addAll(tempArray, num[i], num[j], num[k], num[l]);
                              aList.add(tempArray);
                          }
                      }
          return aList;   
      }
  }
  </code></pre>