Skip to content

Instantly share code, notes, and snippets.

@jutikorn
Created June 29, 2022 00:55
Show Gist options
  • Save jutikorn/f02f898e573f2f77c14b7cbf332bc817 to your computer and use it in GitHub Desktop.
Save jutikorn/f02f898e573f2f77c14b7cbf332bc817 to your computer and use it in GitHub Desktop.
still it doesn't prevent the edge case when nums = [1,1,1,1], target = 4
class Solution {
private List<List<Integer>> result = new ArrayList();
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<Integer> previousNum = new ArrayList();
kSum(previousNum, nums, 4, 0, target);
return result;
}
public void kSum(List<Integer> previousNum, int[] nums, int k, int start, int target) {
if(k > 2) {
for(int i = start; i < nums.length-k+1; i++){
if(i > start && nums[i] == nums[i-1]){
continue;
}
previousNum.add(nums[i]);
kSum(previousNum, nums, k-1, i+1, target - nums[i]);
previousNum.remove(previousNum.size()-1);
}
} else {
int left = start;
int right = nums.length -1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum < target){
left++;
} else if(sum > target){
right--;
} else {
List<Integer> subset = new ArrayList();
subset.addAll(previousNum);
subset.add(nums[left]);
subset.add(nums[right]);
result.add(subset);
left++;
while(left < right && nums[left] == nums[left-1] ){
left++;
}
}
}
}
}
public int sumList(List<Integer> previousNum){
int sum = 0;
if(previousNum != null && !previousNum.isEmpty()){
for(int i = 0; i < previousNum.size(); i++){
sum += previousNum.get(i);
}
}
return sum;
}
}
// -2,-1,0,0,1,2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment