Kolikot

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