Skip to main content

Coin Change Combination

1. You are given a number n, representing the count of coins.

2. You are given n numbers, representing the denominations of n coins.

3. You are given a number "amt".

4. You are required to calculate and print the number of combinations of the n coins using which the 

     amount "amt" can be paid.

Note 1: You have an infinite supply of each coin denomination i.e. same coin denomination can be 

                  used for many installments in payment of "amt"

Note 2: You are required to find the count of combinations and not permutations i.e.

                  2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same 

                  combination. You should treat them as 1 and not 3.

Input Format

A number n

n1

n2

.. n number of elements

A number amt

Output Format

A number representing the count of combinations of coins which can be used to pay the amount "amt"


Constraints

1 <= n <= 30

0 <= n1, n2, .. n elements <= 20

0 <= amt <= 50

Sample Input

4

2

3

5

6

7

Sample Output

2


Solution:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        // input
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = sc.nextInt();
        int amt = sc.nextInt();
        int[] dp = new int[amt+1];
        // process
        dp[0] = 1;
        
        for(int i=0;i<n;i++){
            for(int j=1;j<=amt;j++){
                if(arr[i]<=j)
                    dp[j] += dp[j-arr[i]];
            }
        }
        
        // output
        System.out.println(dp[amt]);
    }
}

Comments

Must Read:

Accenture TFA Quiz | Part 2

  Question  26 Correct Marked out of 1 Flag question Question text What will be the output of the following Java code? public class ApplicationTester { public static void main(String[] args) { int[] array = {11,22,33,44,55,11}; int searchNumber = 11, position=999; for(int index=0; index < array.length; index++) { if(searchNumber == array[index]) { position = index; } } System.out.println(position); } } Choose the most appropriate option. Select one: a.  0 b.  5   c.  1 d.  6 Feedback The correct answer is: 5 Question  27 Incorrect Marked out of 1 Flag question Question text Predict the line of code Abstract class Base1 { protected void getDetails() { System.out.println("Base method"); } public Abstract void demomethod(); } Abstract class Base2 extends Base1 { public Abstract void samplemethod(); } class Derived extends Base2 { //Line1 } Select one: ...

Software Engineering Concepts Software Maintenance Test Your Understanding

  Software Engineering Concepts       Software Maintenance            Test Your Understanding

UNIX Introduction to Unix | Post-Quiz

 UNIX  Introduction to Unix  Post-Quiz  Feedback Congratulations! You have passed by securing more that 80%. Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text  What is the default maximum number of processes that can exist in Unix? Select one: a.  unlimited b.   32768           c.   4096        d.  1024          Feedback Your answer is correct. The correct answer is:  32768         Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text Single user mode shell has _____ prompt.  Select one: a.   $ Normal user  b.  % Admin user c.  ~ Home user d.  # Root user    Feedback Your answer is correct. The correct answer is: # Root user  Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text Predict the output for the following...

RDBMS Data Definition Language | Change the name of the table Sales Info

  RDBMS  Data Definition Language  Change the name of the table Sales Info Write an SQL statement to rename the table Sales Info to Sales_Information. (Hint: use alter command to rename the table name) Evaluation Result: Result Description Summary of tests +------------------------------+ | 1 tests run / 1 test passed | +------------------------------+

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD for Students

  Generate XSD for Students   Generate XSD for the following XML. XYZ School wants to store the details of students in an xml file. The following scenario helps in designing the XML document. Here StudentList  is the root tag. StudentList contains the entry of each student with rollno, name, age, address and department. <?xml version="1.0" encoding="UTF-8"?> <StudentList  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  xsi:noNamespaceSchemaLocation="StudentList.xsd">     <Student rollno="2017CSE0055">         <name>             <firstname>Savitha</firstname>         </name>         <age>20</age>         <address>             <doorno>35</doorno>     ...

Programming using Java Hands On - Control Structures | Bill Generation

Bill Generation Tom went to a movie with his friends in a multiplex theatre and during break time he bought pizzas, puffs and cool drinks.  Consider   the following prices :  Rs.100/pizza Rs.20/puffs Rs.10/cooldrink Generate a bill for What Tom has bought. Sample Input 1: Enter the no of pizzas bought:10 Enter the no of puffs bought:12 Enter the no of cool drinks bought:5 Sample Output 1: Bill Details No of pizzas:10 No of puffs:12 No of cooldrinks:5 Total price=1290 ENJOY THE SHOW!!! Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 6 tests run/ 6 tests passed | +------------------------------+

Web Technology HTML 5 HTML 2 | Quiz 1

 Web Technology       HTML 5            HTML 2               Quiz 1  

Software Engineering Concepts Configuration Management And Version Control Post-Quiz

 Software Engineering Concepts       Configuration Management And Version Control            Post-Quiz

Subscribe to Get's Answer by Email