Im trying to solve a google foobar challenge but I am stuck on how to change this to use recursion. any pointers would be helpful
public static int[] answer(int[] l, int t) {
// convert the array into a list
List<Integer> list = new ArrayList<>();
for (int i : l) {
list.add(i);
}
for (int i = 0; i < list.size(); i++) {
Integer n = list.get(i);
if (i >= 1) {
Integer nMinus1 = list.get(i - 1);
Integer nMinus2;
Integer nMinus3;
Integer nMinus4;
Integer nMinus5;
Integer nMinus6;
if (n + nMinus1 == t) {
// done
return new int[]{i - 1, i};
} else if (i >= 2) {
nMinus2 = list.get(i - 2);
if (n + nMinus1 + nMinus2 == t) {
// done
return new int[]{i - 2, i};
} else if (i >= 3) {
nMinus3 = list.get(i - 3);
if (n + nMinus1 + nMinus2 + nMinus3 == t) {
// done
return new int[]{i - 3, i};
} else if (i >= 4) {
nMinus4 = list.get(i - 4);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 == t) {
// done
return new int[]{i - 4, i};
} else if (i >= 5) {
nMinus5 = list.get(i - 5);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 == t) {
// done
return new int[]{i - 5, i};
} else if (i >= 6) {
nMinus6 = list.get(i - 6);
if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 + nMinus6 == t) {
// done
return new int[]{i - 6, i};
}
}
}
}
}
}
}
}
return new int[]{-1, -1};
}
Here is the question:
Given the list l as [4, 3, 5, 7, 8] and the key t as 12, the function answer(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function answer(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15.
You probably don't need an arraylist. You could perform a double loop on the array l. Why do you want recursion?
You could do something like:
public static int[] answer(int[] l, int t) {
int[] rets = {-1, -1};
int sum=0;
for (int i=0; i<l.length; i++) {
sum=0;
for (int j=i; j<l.length; j++) {
sum+=l[j];
if (sum > t) break;
if (sum == t) {
rets[0] = i;
rets[1] = j;
return rets;
}
}
}
return rets;
}