I solved this problem without recursion.
Here is my algo :
- Check the sum%2, if <>0 then return false where sum=Arrays.stream(A).sum();
- Filter out elements which are less than sum/2. Lets assume we have temp where each element is less than or equal to sum.
- Sort the array. Two variables start =0 and end= temp.length-1, k=sum/2
- for i=0 to N in temp,
- while(k >0 AND start<end)
- if checkSum(temp, start, end, k)==true, return true;
- else k=k-temp[start++]; loop ends
- sum=k, outer loop ends.
Array is sorted , checkSum(temp, start,end,k) searches for the element in the array from index start to end.