[Sum][Two Pointers] 4Sum

1. Example

s=[1, 0 ,-1, 0, -2 ,2] and target sum is 0
A solution set is :
(-1,0,0,1)
(-2,-1,1,2)
(-2,0,0,2)

2. Implementation
Q1: 4 sum take 4 number to sum over and get zero value
A1: size of array less than 4 would be return
Q1: According to rule, fix one and use two pointers to get other two numbers by using two sum, how about 4 ?
A1: We fix two and get other two by twoSum
Q1: how to fix two
A1: fix the last two, or using 4Sum call 3Sum and then call 2Sum

// Time:O(n^3), Space:O(n)
public List> fourSum (int[] num, int target)
{
      List> res = new ArrayList>();
      // validate the input
      if ( num == null || num.length <4 data-blogger-escaped-3="" data-blogger-escaped-always="" data-blogger-escaped-and="" data-blogger-escaped-arrays.sort="" data-blogger-escaped-element="" data-blogger-escaped-fix="" data-blogger-escaped-from="" data-blogger-escaped-i="" data-blogger-escaped-in="" data-blogger-escaped-keep="" data-blogger-escaped-last="" data-blogger-escaped-left="" data-blogger-escaped-note:="" data-blogger-escaped-num="" data-blogger-escaped-one="" data-blogger-escaped-order="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-so="" data-blogger-escaped-solution="" data-blogger-escaped-start="" data-blogger-escaped-the="" data-blogger-escaped-we=""> 2)
      for (int i = num.length -1; i > 2 ; i--)
      {
            // NOTE: when iterating, rule out the duplicate
            if ( i == num.length -1 || num[i] != num[i+1] )
            {
                   List> curRes = threeSum(num, target - num[i], i-1);
                   for (int j = 0; j < curRes.size();j++)
                   {
                        curRes.get(j).add(num[i]);
                   }
                   res.addAll(curRes);
            }
      }

     
      return res;

}


private List> threeSum (int[] nums, int target, int end)
{
       List> res = new ArrayList>();
      //@ validate the input 
      if ( nums==null || nums.length < 3 )
      {
           return res;
      }




      // NOTE: start and end
      for (int i = end; i > 1; i--)
      {    
           // avoid dupliate
           if ( i == end || num[i] != num[i+1] ) 
           {
                 // NOTE : ref = object(new keyword)
                 List> curRes = twoSum(num, target - num[i], i-1);
                 for(int j = 0; j < curRes.size();j++)
                 {
                      curRes.get(j).add(num[i]);
                 } 
                 res.addAll(curRes);
           }
      }

      
      return res;
}


private List> twoSum(int[] num, int target, int end)
{ 
      List> res = new ArrayList>();
      //@ validate the input
      if (  num==null || num.length < 2   )
      {
           return res;
      }


      int l = 0;
      int r =end;
      // NOTE: l and r two separate values
      while(  l < r )
      {
          if ( num[l] + num[r] == target)
          {
                List item = new ArrayList();
                item.add(num[l]);
                item.add(num[r]);
                res.add(item);
                l++;
                r--;
                // Avoid duplicate, should have different solution
                while ( l < r && num[l] == num[l-1] )
                {
                    l++;
                } 
                while ( l < r && num[r] == num[r+1])
                {
                    r--;
                }
          } 
          else if ( num[l] + num[r] > target)
          {
                r--;
          }
          else 
          {
                l++;
          }
      }
      
      return res;

}

3. Similar Ones
Combination Sum II
2Sum
3Sum
3Sum Closest