Given an array of ints and a number n, calculate the number of ways to sum to n using the ints

Question

I saw this problem in my interview preparation.

Given an array of ints and a number n, calculate the number of ways to sum to n using the ints

Following code is my solution. I tried to solve this by recursion. Subproblem is for each int in the array, we can either pick it or not.

public static int count(List<Integer> list, int n) {
    System.out.print(list.size() + ", " + n);
    System.out.println();
    if (n < 0 || list.size() == 0)
      return 0;
    if (list.get(0) == n)
      return 1;
    int e = list.remove(0);
    return count(list, n) + count(list, n - e);
  }

I tried to use [10, 1, 2, 7, 6, 1, 5] for ints, and set n to 8. The result should be 4. However, I got 0. I tried to print what I have on each layer of stack to debug as showed in the code. Following is what I have:

7, 8
6, 8
5, 8
4, 8
3, 8
2, 8
1, 8
0, 8
0, 3
0, 7
0, 2
0, 1
0, 6
0, 7
0, -2

This result confuses me. I think it looks right from beginning to (0, 3). Starting from (0, 7), it looks wrong to me. I expect (1, 7) there. Because if I understand correctly, this is for count(list, n - e) call on second to the bottom layer on the stack. The list operation on the lower layer shouldn't impact the list on the current layer. So my questions are:

1. why is it (0, 7) instead of (1, 7) based on my current code?
2. what adjustment should I do to my current code to get the correct result?

Thanks!

Answer 1

The reason why your algorithm is not working is because you are using one list that is being modified before the recursive calls.

Since the list is passed by reference, what ends up happening is that you recursively call remove until there is nothing in the list any more and then all of your recursive calls are going to return 0

What you could do is create two copies of the list on every recursive step. However, this would be way too inefficient.

A better way would be to use an index i that marks the element in the list that is being looked at during the call:

public static int count(List<Integer> list, int n, int i) {
    //System.out.print(list.size() + ", " + n);
    //System.out.println();
    if (n < 0 || i <= 0)
      return 0;

    int e = list.get(i);  // e is the i-th element in the list
    if (e == n)
      return 1 + count(list, n, i-1);   // Return 1 + check for more possibilities without picking e

    return count(list, n, i-1) + count(list, n - e, i-1);   // Result if e is not picked + result if e is picked
}

You would then pass yourList.size() - 1 for i on the initial function call.

One more point is that when you return 1, you still have to add the number of possibilities for when your element e is not picked to be part of a sum. Otherwise, if - for example - your last element in the list was n, the recursion would end on the first step only returning 1 and not checking for more possible number combinations.

Finally, you might want to rewrite the algorithm using a dynamic approach, since that would give you a way better running time.