Possible combinations of bills that sum to the given amount

Question:


You are given an array that represents bills in certain currency
(for example 1, 2, 5, 10) and an amount, for example 17. You should output
the number of possible combinations of bills that sum to the given amount.

Answer:


{2, 5, 10}

Can I optimize/improve below code? Current complexity is: O(2(n-1)), where n is the bill list length.

//Returns possible Bills List
public static List> possibleBills(Integer amount, int[] bills){
    List> result = new ArrayList>();

    if(amount  set = new TreeSet();
        set.add(bills[0]);
        result.add(set);
        return result;
    }

    //Include 0'th bill and generate possible bills
    List> result1 = possibleBills(amount - bills[0], Arrays.copyOfRange(bills, 1, bills.length));
    if(result1 != null){
        Iterator> result1Itr = result1.iterator();
        while(result1Itr.hasNext()){
            Set set = result1Itr.next();
            set.add(bills[0]);
        }
        result.addAll(result1);
    }

    //exclude 0'th bill and generate possible bills
    List> result2 = possibleBills(amount, Arrays.copyOfRange(bills, 1, bills.length));
    if(result2 != null){
        result.addAll(result2);
    }

    if(result.size() == 0){
        return null;
    }
    return result;
}

You could do some dynamic programming solution.

The basic idea of it in this situation would be you keep track of what you can get with just the 1 dollar bill, then figure out where you can reach with the 2 dollar bill, then the 5 dollar bill. (For the sake of example, I'll use a 7 dollar bill as well as the one's you have in you example)

So, for example you would start with an array of size 18. Because you can reach 0 dollars, you would have

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

then with the 1 dollar bill you can reach 0 dollars and 1 dollar

1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

then with the 2 dollar bill and the 1 dollar bill you can reach 0,1,2,or 3 dollars

1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

then with the 5,2, and 1 dollar bill you can reach 0,1,2,3,5,6,7,or 8 dollars

1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0

then, with the 7 dollar bill: you can reach 7 and 8 in two ways

1,1,1,1,0,1,1,2,2,1,1,0,1,1,1,1,0,0,0

10 dollar bill

1,1,1,1,0,1,1,2,2,1,2,1,2,2,1,2,1,2,2

So, there are two ways to reach 18

StackExchange Code Review Q#10793, answer score: 2