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.

Answer 2

This problem can actually be solved without the use of an additional method. The concept is as follows:

• if list is empty return 0
• if list has 1 item and it is <= limit return item
• if list has 1 item and it is > limit return 0
• if list has more than 1 item and first item is > limit return the max of sublist
• otherwise return the max between max of sublist and first item plus max of sublist with limit minus the first item

public static int maxSum(List<Integer> numbers, int limit) {

      if(numbers.size() == 0){ return 0; }
      int num = numbers.get(0);
      if(numbers.size() == 1){
        if(num > limit){
            return 0;
        }else{
            return num;
        }
      }
      List<Integer> sublist = numbers.subList(1, numbers.size());
      int subMax = maxSum(sublist, limit);
      if(num > limit){ return subMax; }
      int max = num + maxSum(sublist, limit - num);
      return Math.max(max, subMax);

}

Answer 3

Based on @Deximat 's suggestion, I rewrite the code to remove the for loop, and it works!

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

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

            if(index == L.size()){
                return true;
            }
            if(!used[index]){
                used[index] = true;
                if(rec2(L, limit, cur+L.get(index), used, max, index)){
                    max[0] = Math.max(max[0], cur+L.get(index));
//                      return true;
                }
                used[index] = false;
            }

            return rec2(L, limit, cur, used, max, index+1);
        }