# Simple Java Solution for 4 sum, 3 sum, 2 sum, any sum...

• Any improvement is welcome.
Updated: recursive stop at twoSum. Time Complexity of kSum is max( O(n^(k-1)), O(nlogn)).

``````public class Solution {
private List<List<Integer>> nSum(int[] nums, int start, int n, int target){
// target is too small or too large so that there won't be solutions.
if (target < nums[start]*n || target > nums[nums.length - 1]*n){
return result;
}

for (int i = start, end = nums.length - n + 1; i < end; ++i){
// avoid duplicated solutions
if (i > start && nums[i - 1] == nums[i]){
continue;
}

if (n == 2){
int required = target - nums[i];

while(nums[end] > required){
end--;
}
if (nums[end] < required){
continue;
}
if (i >= end){
break;
}

// duplicated solution
if (end + 1 < nums.length && nums[end+1] == nums[end]){
continue;
}

// get two sum
continue;
}

for (List<Integer> list : nSum(nums, i + 1, n - 1, target - nums[i])){
}

}
return result;
}

public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums.length == 0){
return Arrays.asList();
}
Arrays.sort(nums);
return nSum(nums, 0, 4, target);
}
}
``````

• Actually, it's just backtracking. Maybe kind of solution, but the time complexity could be reduced based on the truth that 4 numbers sum.
Backtracking here, is just brute force I think.

• @MrYy Thanks for the comment. Code updated.

• for (int i = start, end = nums.length - n + 1; i < end; ++i)
why end is from nums.length - n + 1, what does this mean?

• @Chaofb You don't need to look for a solution for nSum in an array smaller than n.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.