Problem :-
You are given an array of integers. Count the numbers of ways in which the sum of 4 elements in this array results in zero.
Input:-
Your program should read lines from standard input. Each line consist of comma separated positive and negative integers.
Output:-
Print out the count of the different number of ways that 4 elements sum to zero.
Test 1:-
2,3,1,0,-4,-1
Expected Output:-
2
Test 2:-
0,-1,3,-2
Expected Output:-
1
Solution:-
import java.util.*;
public class Main
{
int len;
public int sum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
List<List<Integer>> list1=helper(nums, target, 4, 0);
return list1.size();
}
private ArrayList<List<Integer>> helper(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(index >= len) {
return res;
}
if(k == 2) {
int i = index, j = len - 1;
while(i < j) {
if(target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target-nums[i]);
res.add(temp);
while(i<j && nums[i]==nums[i+1]) i++;
while(i<j && nums[j-1]==nums[j]) j--;
i++;
j--;
} else if (target - nums[i] > nums[j]) {
i++;
} else {
j--;
}
}
} else{
for (int i = index; i < len - k + 1; i++) {
ArrayList<List<Integer>> temp = helper(nums, target - nums[i], k-1, i+1);
if(temp != null){
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
while (i < len-1 && nums[i] == nums[i+1]) {
i++;
}
}
}
return res;
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
String s= sc.nextLine();
String ar[]=s.split(",");
int ar1[]=new int[ar.length];
int i1=0;
for(String a:ar)
ar1[i1++]=Integer.parseInt(a);
int n=ar1.length;
int count=0;
Main m=new Main();
System.out.print(m.sum(ar1,0));
}
}
