Program crashes, Tree too large

Question

I'm trying to answer this problem as an exercise:

here are set of coins of {50,25,10,5,1} cents in a box.Write a program to find the number of ways a 1 dollar can be created by grouping the coins.

My solution involves making a tree with each edge having one of the values above. Each node would then hold a sum of the coins. I could then populate this tree and look for leaves that add up to 100. So here is my code

class TrieNode
{
public:
    TrieNode(TrieNode* Parent=NULL,int sum=0,TrieNode* FirstChild=NULL,int children=0, bool key =false )
        :pParent(Parent),pChild(FirstChild),isKey(key),Sum(sum),NoChildren(children)
    {
        if(Sum==100)
            isKey=true;
    }
    void SetChildren(int children)
    {
        pChild = new TrieNode[children]();
        NoChildren=children;
    }
    ~TrieNode(void);

    //pointers
    TrieNode* pParent;
    TrieNode* pChild;

    int NoChildren;

    bool isKey;
    int Sum;
};

void Populate(TrieNode* Root, int coins[],int size)
{
    //Set children
    Root->SetChildren(size);

    //add children
    for(int i=0;i<size;i++)
    {
        TrieNode* child  = &Root->pChild[0];
        int c = Root->Sum+coins[i];
        if(c<=100)
        {
            child = new TrieNode(Root,c);

            if(!child->isKey) //recursively populate if not a key
                Populate(child,coins,size);
        }
        else 
            child = NULL;
    }
}

int getNumKeys(TrieNode* Root)
{
    int keys=0;

    if(Root == NULL)
        return 0;

    //increment keys if this is a key
    if(Root->isKey)
        keys++;

    for(int i=0; i<Root->NoChildren;i++)
    {
        keys+= getNumKeys(&Root->pChild[i]);
    }

    return keys;
}

int _tmain(int argc, _TCHAR* argv[])
{
    TrieNode* RootNode = new TrieNode(NULL,0);
    int coins[] = {50,25,10,5,1};
    int size = 5;

    Populate(RootNode,coins,size);
    int combos =  getNumKeys(RootNode);

    printf("%i",combos);

    return 0;
}

The problem is that the tree is so huge that after a few seconds the program crashes. I'm running this on a windows 7, quad core, with 8gb ram. A rough calculation tells me I should have enough memory.

Are my calculations incorrect? Does the OS limit how much memory I have access to? Can I fix it while still using this solution?

All feedback is appreciated. Thanks.

Edit1: I have verified that the above approach is wrong. By trying to build a tree with a set of only 1 coin. coins[] = {1};

I found that the algorithm still failed. After reading the post from Lenik and from João Menighin I came up with this solution that ties both Ideas together to make a recursive solution which takes any sized array

//N is the total the coins have to amount to
int getComobs(int coins[], int size,int N)
{
    //write base cases
    //if array empty | coin value is zero or N is zero
    if(size==0 || coins[0]==0 ||N==0)
        return 0;


    int thisCoin = coins[0];
    int atMost = N / thisCoin ;

    //if only 1 coin denomination
    if(size==1)
    {
        //if all coins fit in N
        if(N%thisCoin==0)
            return 1;
        else
            return 0;
    }


    int combos =0;
    //write recursion
    for(int denomination =0; denomination<atMost;denomination++)
    {
        coins++;//reduce array ptr

        combos+= getComobs(coins, size-1,N-denomination*thisCoin);

        coins--;//increment array ptr
    }

    return combos;
}

Thanks for all the feedback

Answer 1

Tree solution is totally wrong for this problem. It's like catching 10e6 tigers and then let go all of them but one, just because you need a single tiger. Very time and memory consuming -- 99.999% of your nodes are useless and should be ignored in the first place.

Here's another approach:

• notice your cannot make a dollar to contain more than two 50 cents
• notice again your cannot make a dollar to contain more than four 25 cent coins
• notice... (you get the idea?)

Then your solution is simple:

for( int fifty=0; fifty<3; fifty++) {
    for( int quarters=0; quarters<5; quarters++) {
        for( int dimes=0; dimes<11; dimes++) {
            for( int nickels=0; nickels<21; nickels++) {
                int sum = fifty * 50 + quarters * 25 + dimes * 10 + nickels * 5;
                if( sum <= 100 ) counter++;  // here's a combination!!
            }
        }
    }
}

You may ask, why did not I do anything about single cent coins? The answer is simple, as soon as the sum is less than 100, the rest is filled with 1 cents.

ps. hope this solution is not too simple =)

Answer 2

Ok, this is not a full answer but might help you. You can try perform (what i call) a sanity check. Put a static counter in TrieNode for every node created, and see how large it grows. If you did some calculations you should be able to tell if it goes to some insane values.

The system can limit the memory available, however it would be really bizarre. Usually the user/admin can set such limits for some purposes. This happens often in dedicated multi-user systems. Other thing could be having a 32bit app in 64bit windows environment. Then mem limit would be 4GB, however this would also be really strange. Any I don't think being limited by the OS is an issue here.

On a side note. I hope you do realize that you kinda defeated all object oriented programming concept with this code :).