All possible combination

[Minionmin]

The problem is "You are given 3 types of coin, 10, 50 and 100. print all the possible combination that add up to 370". I thought this problem is going to be similar with knapsack problem. I tried to reference and bruteforce the problem but it turns out does not work. What did I do wrong?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>

void possibleOutcome(int coins[], std::vector<int> temp, int money)
{

	if (money == 370)
	{
		for (int i = 0; i < temp.size(); i++)
			printf("%d ", temp[i]);

		printf("\n");
		return;
	}

	for (int i = 0; i < 3; i++)
	{
		temp.push_back(coins[i]);
		possibleOutcome(coins, temp, money+coins[i]);
		temp.pop_back(); //clear the previous value of vector for the next recursion
	}

}

int main(void)
{
	std::vector<int> temp;
	int coins[3] = {10,50,100};
	int ans = 0;

	possibleOutcome(coins, temp, ans);

	return 0;
}

[coder777]

The problem is that when add the values (like all 50) and you will not get exactly 370 you will have an infinite recursion. Try

void possibleOutcome(int coins[], std::vector<int> temp, int money)
{
	if (money > 370)
	  return;
	else if (money == 370)
	{

[lastchance]

That recursive method will lead to an awful lot of repeats.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct wallet
{
   int sum = 0;
   vector<int> sequence;
   friend ostream &operator << ( ostream &out, const wallet &W )
   {
      for ( int i : W.sequence ) out << i << ' ';
      return out;
   }
};

int main()
{
   const int target = 370;
   const vector<int> coins = { 10, 50, 100 };
   queue<wallet> current;   current.push( wallet() );

   while ( !current.empty() )
   {
      wallet p = current.front();
      current.pop();      
      {
         for ( int c : coins )
         {
            if ( !p.sequence.empty() && c < p.sequence.back() ) continue;  // avoid repeats
            int test = p.sum + c;
            if ( test <= target )
            {
               wallet q = p;
               q.sequence.push_back( c );
               q.sum = test;
               if ( test == target ) cout << q << '\n';
               else                  current.push( q );
            }
         }
      }
   }
}

10 10 50 100 100 100 
10 10 50 50 50 100 100 
10 10 50 50 50 50 50 100 
10 10 50 50 50 50 50 50 50 
10 10 10 10 10 10 10 100 100 100 
10 10 10 10 10 10 10 50 50 100 100 
10 10 10 10 10 10 10 50 50 50 50 100 
10 10 10 10 10 10 10 50 50 50 50 50 50 
10 10 10 10 10 10 10 10 10 10 10 10 50 100 100 
10 10 10 10 10 10 10 10 10 10 10 10 50 50 50 100 
10 10 10 10 10 10 10 10 10 10 10 10 50 50 50 50 50 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 100 100 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 50 100 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 50 50 50 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 100 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 50 50 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 100 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 50 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 50 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 

[lastchance]

If you are prepared to restrict yourself to the specific case of 3 coins then you can use just simple loops:

#include <iostream>

int main()
{
   const int target = 370;
   const int a = 100, b = 50, c = 10;
   for ( int i = 0; i <= target / a; i++ )
   {
     for ( int j = 0; j <= ( target - i * a ) / b; j++ )
     {
        int remainder = target - i * a - j * b, k = remainder / c;
        if ( remainder % c == 0 ) std::cout << i << " * " << a << " + " << j << " * " << b << " + " << k << " * " << c << '\n';
     }
   }
}

0 * 100 + 0 * 50 + 37 * 10
0 * 100 + 1 * 50 + 32 * 10
0 * 100 + 2 * 50 + 27 * 10
0 * 100 + 3 * 50 + 22 * 10
0 * 100 + 4 * 50 + 17 * 10
0 * 100 + 5 * 50 + 12 * 10
0 * 100 + 6 * 50 + 7 * 10
0 * 100 + 7 * 50 + 2 * 10
1 * 100 + 0 * 50 + 27 * 10
1 * 100 + 1 * 50 + 22 * 10
1 * 100 + 2 * 50 + 17 * 10
1 * 100 + 3 * 50 + 12 * 10
1 * 100 + 4 * 50 + 7 * 10
1 * 100 + 5 * 50 + 2 * 10
2 * 100 + 0 * 50 + 17 * 10
2 * 100 + 1 * 50 + 12 * 10
2 * 100 + 2 * 50 + 7 * 10
2 * 100 + 3 * 50 + 2 * 10
3 * 100 + 0 * 50 + 7 * 10
3 * 100 + 1 * 50 + 2 * 10

[George P]

@Minionmin, A couple of suggestions:

1. When using C library functions in C++ code use the C++ version of the header, if there is one available. <cstdio> instead of <stdio.h>

2. Prefer using C++ functionality instead of C functions, when available. C++20 now has output formatting that is similar to C printf. <format> is the header.

I see you are using a version of Visual Studio, the #define _CRT_SECURE_NO_WARNINGS is a dead giveaway for that. If you use VS 2019 or 2022 std::format is available, currently the only compiler suite that is compliant.

https://en.cppreference.com/w/cpp/utility/format

<format> is largely based on the 3rd party {fmt} library so if you use another compiler you can still get that formatting capability.

https://fmt.dev/latest/index.html

#include <iostream>
#include <format>

int main()
{
   unsigned int limit {};

   std::cout << "This program calculates n! and the sum of the integers\n"
             << "up to n for values 1 to limit.\n";
   std::cout << "What upper limit for n would you like? ";
   std::cin >> limit;
   std::cout << '\n';

   // The format string for all rows of the table
   const auto table_format { "{:>8} {:>8} {:>20}\n" };

   // output column headings
   std::cout << std::format(table_format, "integer", "sum", "factorial");

   for ( unsigned long long n { 1 }, sum {}, factorial { 1 }; n <= limit; ++n )
   {
      sum       += n; // accumulate sum to current n
      factorial *= n; // calculate n! for current n

      std::cout << std::format(table_format, n, sum, factorial);
   }
}

This program calculates n! and the sum of the integers
up to n for values 1 to limit.
What upper limit for n would you like? 15

 integer      sum            factorial
       1        1                    1
       2        3                    2
       3        6                    6
       4       10                   24
       5       15                  120
       6       21                  720
       7       28                 5040
       8       36                40320
       9       45               362880
      10       55              3628800
      11       66             39916800
      12       78            479001600
      13       91           6227020800
      14      105          87178291200
      15      120        1307674368000

Since std::format requires C++20 to work, let's use modules instead of headers. Change the 2 #includes to:

import <iostream>;
import <format>;

The program output is the same.