// O(n^3)
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num ,int target) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for( int i = 0; i < num.length; i++){
for (int j = i+1; j < num.length; j++) {
for (int k = j+1, l = num.length-1; k < l;) {
int s = num[l] + num[i] + num[j] + num[k];
if (s == target) {
ArrayList<Integer> x = new ArrayList<Integer>();
x.add(num[i]);
x.add(num[j]);
x.add(num[k]);
x.add(num[l]);
result.add(x);
k++;
l--;
}
else if (s > target) {
l--;
}
else{
k++;
}
}
}
}
return result;
}
}