「お題：ある金額になるコインの組み合わせ」をJavaで挑戦してみた

お題：ある金額になるコインの組み合わせ - No Programming, No Life

TL眺めてたらまたお題が出てたので取り敢えず正攻法？でやってみた

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Odai{

    public static List<List<Integer>> hoge( int sum, List<Integer> coinList ){
        
        Deque<Integer> stack = new LinkedList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Collections.sort( coinList );
        hoge( sum, coinList, stack, res );
        
        return res;
        
    }
    
    private static void hoge( int sum, List<Integer> coinList, Deque<Integer> stack, List<List<Integer>> res ){
        int max = stack.size() > 0 ? stack.peek() : coinList.get( coinList.size() - 1 ) < sum ? coinList.size() - 1  : sum;
        
        if( sum == 0 ){
            res.add( new ArrayList<Integer> ( stack ) );
            return;
        }
        for( int coin : coinList ){
            if( coin > max )continue;
            stack.push( coin );
            sum -= coin;
            hoge( sum, coinList, stack, res );
            sum += stack.pop();
        }
    }
}

テストコード

import java.util.Arrays;
import java.util.List;
import junit.framework.TestCase;

public class OdaiTest extends TestCase{
    
    public void testHoge(){
        List<List<Integer>> res;
        
        res = Odai.hoge( 10, Arrays.asList( 1, 5, 10, 50, 100, 500 ) );
        
        assertEquals( Arrays.asList( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ), res.get( 0 ) );
        assertEquals( Arrays.asList( 1, 1, 1, 1, 1, 5 ), res.get( 1 ) );
        assertEquals( Arrays.asList( 5, 5 ), res.get( 2 ) );
        assertEquals( Arrays.asList( 10 ), res.get( 3 ) );

        res = Odai.hoge( 16, Arrays.asList( 2, 8, 10 ) );

        assertEquals( Arrays.asList( 2,2,2,2,2,2,2,2 ), res.get( 0 ) );
        assertEquals( Arrays.asList( 2,2,2,2,8 ), res.get( 1 ) );
        assertEquals( Arrays.asList( 8,8 ), res.get( 2 ) );
        assertEquals( Arrays.asList( 2,2,2,10 ), res.get( 3 ) );

        res = Odai.hoge( 15, Arrays.asList( 2, 8, 10 ) );

        assertEquals( 0, res.size() );

    }
}

2011-09-05追記
確かにご指摘のあった通り、上のコードは明らかにおかしい。テストコード通ったのが奇跡的なレベル。
コインの最大値を返す所(下のコードの削除部)が、coinList.size() - 1 というインデックスとなるべき値を返してしまってました。
int max = stack.size() > 0 ? stack.peek() : coinList.get( coinList.size() - 1 ) < sum ? coinList.size() - 1 : sum;

あともう一点、このままだとstack.peek() の値がsum(残りの金額)の値を超えてしまう可能性があります。
あえて一行のままで直すなら下記のコードに置き換えればいいはず。
int max = stack.size() > 0 ? stack.peek() < sum ? stack.peek() : sum : coinList.get( coinList.size() - 1 ) < sum ? coinList.get( coinList.size() - 1 ) : sum;

教訓：テスト大事！