I've tried recursion at my first attempt. It always gets TLE. I look into the run time and I think it is O(n!), which is not a linear time. Here is my code.

```
public class Solution {
List<List<Integer>> output = new ArrayList<List<Integer>>();
HashSet<List<Integer>> visited = new HashSet<List<Integer>>();
final static int pivot = 4;
public List<List<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
search(0,target,0,num, new ArrayList<Integer>());
return output;
}
private void search(int sum, int target, int index, int[] num, List<Integer> lst){
if(lst.size()==pivot){
if(sum == target)
if(!visited.contains(lst)){
visited.add(lst);
output.add(lst);
}
return;
}
if(sum + (pivot-lst.size())*num[num.length-1] < target){return;}
if(sum + (pivot-lst.size())*num[index] > target){return;}
for(int i = index;i <= num.length-(pivot-lst.size());i++){
if(sum + (pivot-lst.size())*num[i] > target){return;}
List<Integer> newlst = new ArrayList<Integer>(lst);
newlst.add(num[i]);
search(sum + num[i], target, i+1, num, newlst);
}
return;
}
}
```