Program crashes, Tree too large

c++, recursion, tree

Solution

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 =)

Problem

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

Original source