Working on a recursion problem in java?

Let's speak generically as it usually makes recursion easier.

If arr[m] < target then see if arr[m+1] < target.

If arr[m] + arr[m+1] < target then see if arr[m] + arr[m+1] + arr[m+1+1] < target.

If arr[m] + arr[m+1] + arr[m+1+1] < target then see if arr[m] + arr[m+1] + arr[m+1+1] + arr[m+1+1+1] < target.

This expansion reduces quite easily to something more along the lines of...

if (curr_sum + arr[index+1]) < target

However, if arr[m] + arr[m+1] + arr[m+2] > target then we need to backtrack to the last known good state arr[m] + arr[m+1] and skip arr[m+2] and try arr[m+3] and so on. This lends itself quite well to a for loop.

If at any point the resultant value of any of these calls is true then quit because you've found some combination of values that sums to your target.

For an example with an array from 0->6:

arr[0] < target
    arr[0] + arr[1] < target
        arr[0] + arr[1] + arr[2] > target 
        arr[0] + arr[1] + arr[3] > target
        arr[0] + arr[1] + arr[4] < target
            arr[0] + arr[1] + arr[4] + arr[5] > target
            arr[0] + arr[1] + arr[4] + arr[6] > target
            // Reached end of array, nothing will work with arr[0] + arr[1] + arr[4]
        arr[0] + arr[1] + arr[5] > target
        arr[0] + arr[1] + arr[6] > target
        // Reached end of array, nothing will work with arr[0] + arr[1]
    arr[0] + arr[2] < target
        arr[0] + arr[2] + arr[3] == target
        // Target found, return true all the way up, breaking out of loops as you go
/r/learnprogramming Thread Parent