CoinChange1

    // This can be used for getting the output in the form of coin used, number of coins
    //But this is not efficient as the DP approach, but can be used if the output is specific as said above
    //Time complesxity O (amount ^coins.Length)
    public Dictionary<int,int> CoinChange1(int[] coins, int amount){
        
        var q = new Queue< Tuple<int,int,Dictionary<int,int>>>();
        q.Enqueue(new Tuple<int,int,Dictionary<int,int>>(amount,0, new Dictionary<int,int>()) );
        
        int mincnt = amount+1;
        var visited = new bool[amount+1];
  
        
        while(q.Count>0){
            
            var t = q.Dequeue();
            var amt = t.Item1;
            var cnt = t.Item2;
            var dict = t.Item3;
            
            if(amt ==0){
               return dict;
            }
            
            if( !visited[amt]){
                for(int i =0; i< coins.Length; i++){
                    if(coins[i] > amt){
                        continue;
                    }

                    var dict1 = dict.ToDictionary(x=>x.Key,x=>x.Value);
                    if(dict1.ContainsKey(coins[i])){
                        dict1[coins[i]]++;
                    }
                    else{
                        dict1.Add(coins[i],1);
                    }
                     q.Enqueue(new Tuple<int,int,Dictionary<int,int>>(amt - coins[i],cnt+1,dict1) );

                }
            }
            
            visited[amt] = true;
            
            
        }
        
      
        
        return new Dictionary<int,int>();
    }