11. Find all four sum numbers

11. Find all four sum numbers

Problem link :- click here

package program;

import java.util.ArrayList;
import java.util.Arrays;

public class Searching__11
{

	/*
	 	Given an array of integers and another number. Find all the unique quadruple
	 	from the given array that sums up to the given number
	 			arr[] = {0, 0, 2, 1, 1}	sum = k
	 			output : 0, 0, 1, 2
	 			
	 	lets sort the array first 
	 	and then take two elements from two for loops 
	 	and the use two pointer approach inside that 
	 */
	
	static ArrayList<ArrayList<Integer>> fourSum(int arr[], int n, int sum)
	{
		//this is our output
		ArrayList<ArrayList<Integer>> result = new ArrayList<>();
		
		//sorting the array
		Arrays.sort(arr);
		
		//taking two elements from two for loops and other two from 
		//two pointer approach
		for(int i=0; i<=n-4; i++)
		{
			for(int j=i+1; j<=n-3; j++)
			{
				int left, right;
				left = j+1;
				right = n-1;
				
				while(left < right)
				{
					int sum1 = arr[i] + arr[j] + arr[left] + arr[right];
					if(sum == sum1)
					{
						ArrayList<Integer> temp = new ArrayList<>();
						temp.add( arr[i] );
						temp.add( arr[j] );
						temp.add( arr[left] );
						temp.add( arr[right] );
						
						result.add(temp);
						left++;
					}
					else if(sum < sum1)
						right--;
					else
						left++;
				}
			}
		}
		
		return result;
	}
	
	
	public static void main(String[] args)
	{
		int arr[] = {10, 2, 3, 4, 5, 7, 8};
		int sum = 23;
		
		ArrayList<ArrayList<Integer>> ans = fourSum(arr, arr.length, sum);
		
		System.out.println("The possible sums are : ");
		System.out.println(ans);
	}

}

Time complexity :- O(n^3)
Space complexity :- O(n^2)