Explanation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, 4, target);
}
private List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (k == 2) { // two pointers from left and right
int l = start, r = len - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
List<Integer> path = new ArrayList<Integer>();
path.add(nums[l]);
path.add(nums[r]);
res.add(path);
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
} else if (sum < target) {
l++;
} else {
r--;
}
}
} else {
for (int i = start; i < len - k + 1; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
}
return res;
}
}