Possible combinations of bills that sum to the given amount

Question

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<Set<Integer>> possibleBills(Integer amount, int[] bills){
    List<Set<Integer>> result = new ArrayList<Set<Integer>>();

    if(amount < 0){
        return null; 
    }

    if(bills.length == 0){
        return null;
    }

    if(amount-bills[0] == 0){
        Set<Integer> set = new TreeSet<Integer>();
        set.add(bills[0]);
        result.add(set);
        return result;
    }

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

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

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

Answer 1

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

Answer 2

Just two random notes:

1. Instead of returning with null I'd throw IllegalArgumentException with a detailed error message when amount < 0 or bills.length == 0. The message would help debugging and would not cause NullPointerExceptions later when somebody try to use the returned value.

2. You also should not return with null when result.size() is zero. From Effective Java, 2nd Edition, Item 43: Return empty arrays or collections, not nulls:

   In summary, there is no reason ever to return null from an array- or collection-valued method instead of returning an empty array or collection.

Answer 3

Here's a more traditional (heavyweight) OOP treatment of the problem. Note that it produces duplicates due to permutations. The fix is to change BillSetList into BillSetSet or manually remove duplicates at the end. Both classes are immutable to make the code safer. You could also clean some of it up a bit by using Guava's collection helper methods.

import java.util.*;

class BillSet
{
    static final BillSet EMPTY = new BillSet();

    final Set<Integer> bills;

    BillSet() {
        this(new TreeSet<Integer>());
    }

    BillSet(int bill) {
        this(Collections.singleton(bill));
    }

    BillSet(int... bills) {
        this(new TreeSet<Integer>());
        for (int bill : bills) {
            this.bills.add(bill);
        }
    }   

    BillSet(Set<Integer> bills) {
        this.bills = bills;
    }

    BillSet with(int bill) {
        if (bills.contains(bill)) {
            return this;
        }
        if (bills.isEmpty()) {
            return new BillSet(bill);
        }
        Set<Integer> newBills = new TreeSet<Integer>();
        newBills.addAll(bills);
        newBills.add(bill);
        return new BillSet(newBills);
    }

    BillSet without(int bill) {
        if (!bills.contains(bill)) {
            return this;
        }
        if (bills.size() == 1) {
            return EMPTY;
        }
        Set<Integer> newBills = new TreeSet<Integer>();
        newBills.addAll(bills);
        newBills.remove(bill);
        return new BillSet(newBills);
    }

    BillSetList subsetsAddingTo(int sum) {
        if (bills.isEmpty()) {
            return BillSetList.EMPTY;
        }
        BillSetList subsets = new BillSetList();
        for (int bill : bills) {
            if (bill == sum) {
                subsets = subsets.with(new BillSet(bill));
            }
            else if (bill < sum) {
                subsets = subsets.with(without(bill).subsetsAddingTo(sum - bill).with(bill));
            }
        }
        return subsets;
    }

    void print() {
        for (int bill : bills) {
            System.out.print(bill + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BillSet set = new BillSet(1, 2, 5, 10);
        BillSetList subsets = set.subsetsAddingTo(17);
        subsets.print();
    }
}

class BillSetList
{
    static final BillSetList EMPTY = new BillSetList();

    final List<BillSet> sets;

    BillSetList() {
        this(new ArrayList<BillSet>());
    }

    BillSetList(List<BillSet> sets) {
        this.sets = sets;
    }

    BillSetList(BillSet... sets) {
        this();
        for (BillSet set : sets) {
            this.sets.add(set);
        }
    }

    BillSetList with(int bill) {
        if (sets.isEmpty()) {
            return this;
        }
        List<BillSet> newSets = new ArrayList<BillSet>(sets.size());
        for (BillSet set : sets) {
            newSets.add(set.with(bill));
        }
        return new BillSetList(newSets);
    }

    BillSetList with(BillSet set) {
        return with(new BillSetList(set));
    }

    BillSetList with(BillSetList otherSets) {
        if (sets.isEmpty()) {
            return otherSets;
        }
        if (otherSets.sets.isEmpty()) {
            return this;
        }
        List<BillSet> newSets = new ArrayList<BillSet>(sets.size() + otherSets.sets.size());
        newSets.addAll(sets);
        newSets.addAll(otherSets.sets);
        return new BillSetList(newSets);
    }

    void print() {
        for (BillSet set : sets) {
            set.print();
        }
    }
}