title: Hackerrank Mark and Toys Question my solution not working for large input testcases
body: <p>Below is the problem statement from hackerrank</p>
  
  <p>Mark and Jane are very happy after having their first child. Their son loves toys, so Mark wants to buy some. There are a number of different toys lying in front of him, tagged with their prices. Mark has only a certain amount to spend, and he wants to maximize the number of toys he buys with this money.</p>
  
  <p>Given a list of prices and an amount to spend, what is the maximum number of toys Mark can buy? For example, if prices = [1,2,3,4]  and Mark has k=7 to spend, he can buy items [1,2,3]  for 6, or [3,4]  for 7 units of currency. He would choose the first group of 3 items.</p>
  
  <p>Below is code I wrote for this problem which involves backtracking technique</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Collections;
  
  public class MarkAndToys {
  
      static ArrayList&lt;Integer&gt; possibleSolutions = new ArrayList&lt;&gt;();
  
      static boolean findSolution(int[] prices,int amount,int left,int length,int items){
  
          // Base case: if whole array was iterated and amount is &gt;=0 then we got a solution
          if(left &gt;= length){
           if(amount&gt;=0){
               possibleSolutions.add(items);
               return true;
           }
           return false;
          }
  
          // Key idea: prices[left] is chosen or it is not.
          // Deal with prices[left], letting recursion
          // deal with all the rest of the array.
  
          // Recursive call trying the case that prices[left] is chosen --
          // subtract it from amount in the call.
          if (findSolution(prices,amount-prices[left],left+1,length,items+1)) return true;
  
          // Recursive call trying the case that prices[left] is not chosen.
          if (findSolution(prices,amount,left+1,length,items)) return true;
  
          // If neither of the above worked, it's not possible.
          return false;
      }
  
      // Complete the maximumToys function below.
      static int maximumToys(int[] prices, int k) {
          if(findSolution(prices,k,0,prices.length,0)){
              //if solutions are found then return maximum of them
              return Collections.max(possibleSolutions);
          }
          return 0;
      }
  
  
  
      public static void main(String[] args) {
          System.out.println(maximumToys(new int[]{1,12,5,111,200,1000,10}, 50));
      }
  
  }
  </code></pre>