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.

{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>();
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();
}
}

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

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

• I assume this is somewhat theoretical problem, because for anything real-world A) you could make some assumptions, B) You are not likely to have to support Zimbabwean dollars that experienced high inflation; maybe only USD, C) You can get away with giving change using only 1s, 2s, 5s, 10s, 20s, 50s, 100s, 200s, 500s, ... (some of these might not exist), so you can actually use a greedy algorithm. I just got a change of (2 $5 bills instead of a single$10) this morning from an auto-register and I did not complain. The complexity almost does not matter; with cash-back limits it is actually O(1). Commented Jul 23, 2012 at 18:03

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

• What would be the time complexity of your algorithm? Commented Apr 12, 2012 at 20:34
• Well, it would be, when optimized, O(n*s), where n is in the number of bills and s is the target amount. But I think you could probably optimize it to O(n^2)
– Jay
Commented Apr 13, 2012 at 0:46

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.

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) {
}
}

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>();
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.remove(bill);
return new BillSet(newBills);
}

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) {
}
}
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);
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) {
}
}

BillSetList with(int bill) {
if (sets.isEmpty()) {
return this;
}
List<BillSet> newSets = new ArrayList<BillSet>(sets.size());
for (BillSet set : sets) {
}
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());