Automatically add items from an array

Question

I have those values:

x = 5;

long[] b = new long[]{5,1,2,3};

I need to make a program that adds the array items b so that the result is always 5(x). You can repeat items, like: [1,1,1,1,1] or [5] or [2,3] or [1,1,3] or [1,1,1,2] or [2,2,1] so the output would be 6, the answer should be any number of possibilities. My doubt would be how to make that sum separately.

EDIT1

That’s the original problem

You are Working at the cash counter at a fun-fair, and you have Different types of Coins available to you in Infinite Quantities. The value of each Coin is already Given. Can you determine the number of Ways of making change for a particular number of Units using the Given types of Coins?

For example, if you have types of Coins, and the value of each type is Given as respectively, you can make change for Units in three Ways: , , and .

Complete the Function getWays that takes the number of Coin types and the value of each Coin type as input, and Return the number of Ways to make change for Units using any number of Coins.

Input Format

The first line contains two space-separated integers describing the respective values of and , Where: is the number of Units is the number of Coin types The Second line contains space-separated integers describing the respective values of each Coin type : (the list of distinct Coins available in Infinite Amounts).

Constraints

Each is Guaranteed to be distinct. Hints

Solve overlapping subproblems using Dynamic Programming (DP): You can Solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and Reference Previously computed Solutions to avoid solving the same subproblem Multiple times. * Consider the degenerate cases: - How Many Ways can you make change for cents? - How Many Ways can you make change for cents if you have no Coins? * If you’re having Trouble Defining your Solutions store, then think about it in Terms of the base case . - The Answer may be Larger than a -bit integer.

Output Format

Print a long integer denoting the number of Ways we can get a sum of from the Given Infinite Supply of types of Coins.

Sample Input 0

4 3

1 2 3

Sample Output 0

4

Explanation 0

There are four Ways to make change for using Coins with values Given by :

Thus, we print as our Answer.

Sample Input 1

10 4

2 5 3 6

Sample Output 1

5

Explanation 1

There are five Ways to make change for Units using Coins with values Given by :

Thus, we print as our Answer.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static long getWays(long n, long[] c){
        // Complete this function
    }

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int m = Convert.ToInt32(tokens_n[1]);
        string[] c_temp = Console.ReadLine().Split(' ');
        long[] c = Array.ConvertAll(c_temp,Int64.Parse);
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        long ways = getWays(n, c);
    }
}
​

Answer 1

The algorithm that satisfies your request is trivial to be implemented. Here is an example I wrote:

// Essa função gera recursivamente toda a árvore de possibilidades para
// todos os trocos iguais ou menos que o objetivo.
static int GetWays(int objetivo, IEnumerable<int> moedas, int trocoParcial)
{
    // Se o troco parcial é o troco que procuramos, então este caminho
    // na árvore de possibilidades é uma resposta válida.
    if (trocoParcial == objetivo)
    {
        return 1;
    }

    // Se já não houver mais moedas ou se o troco parcial ultrapassar
    // o troco que procuramos, significa que esse caminho na árvore de
    // possibilidades não nos levou a uma resposta válida.
    if (!moedas.Any() || trocoParcial > objetivo)
    {
        return 0;
    }

    // Se não foi possível decidir se a resposta é ou não válida, temos
    // que recursivamente verificar as alternativas que seguem ambos os
    // galhos. Vamos somar todas as respostas válidas para todas as
    // possíveis alternativas que podemos tomar.:
    return GetWays(objetivo, moedas, trocoParcial + moedas.First()) + GetWays(objetivo, moedas.Skip(1), trocoParcial);
}

I put several comments along the code to help in understanding, although it probably won’t be necessary as it’s a rather simplistic algorithm. All it does is recursively generate all possible changes, accumulating +1 if the change is valid (equal to the goal), or +0 otherwise.

Observing the code you can quickly visualize that this function would generate a binary tree (the possibilities tree). The tree is binary because a choice of 2 possibilities is made for each nonterminal node:

• the coin is used in the change; or
• The coin is not used in change

Now it’s obvious the work done on each of the recursive calls and why there are exactly two calls.

However, as explained in the English text that you asked the question, this implementation is extremely inefficient, as the whole possibility tree is accumulated in the stack of the computer.

The analysis of the computational complexity of the above function will be left as an exercise you solve if you are interested (and I strongly recommend that you do).

The English text still gives an excellent tip on how to avoid stack build-up. You should follow from there.

I gave you a functional solution. Now you just need to make it performative.

I hope my code code and my explanation can help you and other browsers.

Hug and good luck!