1

I'm sorry if this is a silly question. I have written the following piece of code for coin change problem.

#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int amount)
{
int combinations[amount + 1];
combinations[0] = 1;

int start;
for(int i = 0; i < n; i++)
{
    start = coins[i];
    int coin = coins[i];
    for(int j = start; j < amount + 1; j++)
    {
        if(j >= coin)
        {
            combinations[j] += combinations[j - coin];
        }
    }
    for(int j = 0; j < amount + 1; j++)
        cout << combinations[j] << " ";
    cout << endl;
}

return combinations[amount];
}

int main(int argc, char const *argv[])
{
int coins[] = {1, 2, 5};
int n = sizeof(coins)/sizeof(coins[0]);

int amount = 12;

// cout << "Total combinations: ";
cout << coinChange(coins, n, amount) << endl;

return 0;
}

The code works fine and provides me the correct output as shown below.

1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 2 2 3 3 4 4 5 5 6 6 7 
1 1 2 2 3 4 5 6 7 8 10 11 13 
13

However, If I uncomment the line cout << "Total combinations: "; just above the function calling in the main function, the program gives me bizzare outputs.

Total combinations: 1 32768 32768 32768 44137 44137 44137 44137 196418491 196418492 -790461916 -790429149 619621115 
1 32768 32769 65536 76906 109673 121043 153810 196539534 196572302 -593922382 -593856847 25698733 
1 32768 32769 65536 76906 109674 153811 186579 196605070 196649208 -593812708 -593703036 25885312 
25885312

Is executing cout before function calling causing this random outputs? Or is this a problem for my version of compiler?

MD Abid Hasan
  • 309
  • 1
  • 3
  • 13
  • I get incorrect output either way. Must be something undefined somewhere. –  May 18 '17 at 01:53
  • Using unitialized values is undefined behavior, random values is one possible outcome see [Is uninitialized local variable the fastest random number generator?](http://stackoverflow.com/a/31746063/1708801) – Shafik Yaghmour May 18 '17 at 03:49

2 Answers2

2

What about initialize (to zero?) combinations ?

Something like

int combinations[amount + 1] {};

Otherwise the initial values of combinations[i] are undefined indeterminate, so are is undefined the final values behavior of the program (correction from Shafik Yaghmour; thanks!)

max66
  • 63,246
  • 10
  • 70
  • 107
1

Do this in your coinChange function.

int combinations[amount + 1]{};
combinations[0] = 1;

int start;
for(int i = 0; i < n; i++)
{
    start = coins[i];
    int coin = coins[i];
    for(int j = start; j < amount + 1; j++)
    {
        if(j >= coin)
        {
            combinations[j] += combinations[j - coin];
        }
    }
    for(int j = 0; j < amount + 1; j++)
        cout << combinations[j] << " ";
    cout << endl;
}

Now uncomment the line and run. The basic problem is when you create the combinations array, you have to initialize the elements to 0. If you don't, they may be all 0 by a lucky coincidence, but you can't guarantee that.

EDIT : Using empty initializer list to initilize array with zeros as max66 suggested.

nakiya
  • 13,523
  • 20
  • 75
  • 116