Sinulla on n kolikkoa ja jokaisella kolikolla on jokin kokonaislukuarvo. Tehtäväsi on laskea, montako eri summaa voit muodostaa käyttämällä kolikoita.

Esimerkiksi kun kolikot ovat [3,4,5], mahdolliset summat ovat 3, 4, 5, 7, 8, 9 ja 12. Tässä tapauksessa on siis 7 mahdollista summaa. Huomaa, että summassa tulee olla vähintään yksi kolikko eli tyhjä ratkaisu ei kelpaa.

Voit olettaa, että 1 \le n \le 100 ja jokaisen kolikon arvo on välillä 1 \dots 100

Python

Toteuta tiedostoon coins.py funktio count, joka antaa mahdollisten summien lukumäärän.

def count(t):
    # TODO

if __name__ == "__main__":
    print(count([3,4,5])) # 7
    print(count([1,1,2])) # 4
    print(count([2,2,2,3,3,3])) # 13
    print(count([42,5,5,100,1,3,3,7])) # 91

Java

Toteuta tiedostoon Coins.java metodi count, joka antaa mahdollisten summien lukumäärän.

public class Coins {
    public int count(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        Coins c = new Coins();
        System.out.println(c.count(new int[]{3,4,5})); // 7
        System.out.println(c.count(new int[]{1,1,2})); // 4
        System.out.println(c.count(new int[]{2,2,2,3,3,3})); // 13
        System.out.println(c.count(new int[]{42,5,5,100,1,3,3,7})); // 91
    }
}