Given a list and a limit, use Recursive/Backtracking algorithm find max sum

Question

This is not a homework, just a self-practice on recursion. :)

The problem: (http://practiceit.cs.washington.edu/problem.jsp?category=Building+Java+Programs%2C+3rd+edition%2FBJP3+Chapter+12&problem=bjp3-12-e21-maxSum)

Given a integer List L and a limit n, find the maxSum(L,n) that does not exceed the limit n. Example, L=[7, 30, 8, 22, 6, 1, 14], and Limit n=19, then the maxSum(L,n)=16. Because the max combination is 7+8+1=16.

I've figured out the classical backtracking algorithm to solve this problem:

    public static int maxSum(List<Integer> L, int limit){
        boolean[] used = new boolean[L.size()];
        int[] max = {0};
        rec(L, limit, 0, used, max);
        return max[0];
    }

    public static boolean rec(List<Integer> L, int limit, int cur, boolean[] used, int[] max){
        if(cur > limit){
            return false;
        } 

        for(int i=0; i<L.size(); i++){
            if(!used[i]){
                used[i] = true;
                if(rec(L, limit, cur+L.get(i), used, max)){
                    max[0] = Math.max(max[0], cur+L.get(i));
                }
                used[i] = false;
            }
        }
        return true;
    }

However, since this problem does not allow any loop in the program. So I'm wondering if there is way to remove the for loop in my rec() function. Thank you very much!

Answer 1

Of course it is possible, every loop can be replaced with recursion.

for(int i = 0; i < size; i++) {
  // some code goes here
}

We can do iterations with following recursive function:

private void iterate(int i, int size) {
  if (i == size){
    return;
  }
  // some code goes here
  iterate(i+1, size);
}

And starting call would be:

iterate(0, size);

That would execute some code for every i 0..size.