Scope
static int[] solve(int arr[], int i, int esum, int csum, int size) {
You leave this as the default scope. For Java, this is package private.
In this case, I would go with
private static int[] solve(int arr[], int i, int esum, int csum, int size) {
The reason being that three of these parameters (i
, csum
, size
) reflect internal knowledge of how the method works. So I would make this private
to make it clear that only people editing this class should use this method. I would then add an additional method:
public static int[] solve(int targetSum, int... numbers) {
return solve(numbers, numbers.length, targetSum, 0, 0);
}
This offers a public face to the private implementation.
I find names like numbers
and targetSum
easier to read than arr
and esum
. In fact, I still don't know what esum
is except by inspecting what it does. Ideally, names should make it easier for me to understand the code.
This also allows solve
to be called in more ways. You can still call it
solve(108, arr);
But you can also say
solve(108, 70, 30, 33, 23, 4, 4, 34, 95, -50, -10, -10, -7);
If that happens to be easier.
This may not matter in real usage, but often it's easier to test in the latter form.
Object oriented
I would also consider making a class to hold the solution. As is, the solution is held in a magic version of an int
array. What's in the array? Which element is which? Again, we have to go read the code to know. I'd rather just be able to read an interface. E.g.
public class PartialSum {
private int distance;
private int count;
public PartialSumDistance(int distance, int count) {
this.distance = distance;
this.count = count;
}
public getDistance() {
return distance;
}
public getSize() {
return count;
}
}
Now, instead of saying a1[0]
, I can say a1.getDistance()
, which is much clearer about what is being discussed.
Optimizing the end condition
if (i == 0) {
Consider
if (i == 0 || esum == csum) {
If we have found a matching partial sum, we can never get closer to a solution. We can only add additional items. But smaller solutions are better. So once we've found a matching sum, we can return. This branch has nothing more to show us. We've already found the best solution that it could find.
Sorting
If the input array were sorted (ascending), we could say
if (csum < esum && arr[i - 1] < 0) {
And return the current solution. We are currently as close to a solution as we could be.
Overall, there are \$2^n\$ sums to check where \$n\$ is the number of items in the array. This is because each item can either be in or not in the sum. So enumerating all the sums is \$\mathcal{O}(2^n)\$. Sorting is only \$\mathcal{O}(n \log n)\$. So we can sort for a trivial cost compared to the overall time to process the problem. Meanwhile, we can potentially prune \$2^i\$ checks, where i
is the number of elements remaining in the array as we process it. Since i
is potentially equal to \$n\$, this seems worthwhile.
Further optimization
To optimize further, we'd need to know more about how the data was meant to be used. For example, if the number of targets to search is larger relative to \$2^n\$, it might make sense to pregenerate all the partial sums and put them in a NavigableMap
or NavigableSet
. Then we could just fetch the appropriate value. But that would be a lousy solution if we're only going to look up one target per array.