Hackerrank Mark and Toys Question my solution not working for large input testcases

Question

Below is the problem statement from hackerrank

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.

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.

Below is code I wrote for this problem which involves backtracking technique

import java.util.ArrayList;
import java.util.Collections;

public class MarkAndToys {

    static ArrayList<Integer> possibleSolutions = new ArrayList<>();

    static boolean findSolution(int[] prices,int amount,int left,int length,int items){

        // Base case: if whole array was iterated and amount is >=0 then we got a solution
        if(left >= length){
         if(amount>=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));
    }

}

Answer 1

This seems to be working fine:

// Complete the maximumToys function below.
static int maximumToys(int[] prices, int k) {
    Arrays.sort(prices);
    int sum = 0;
    int index = 0;
    for(int i = 0; i < prices.length; i++) {
        sum+=prices[i];
        index = i;
        if(sum > k) {
            break;
        }
    }

    return index;

}