Algorithm or solution for selecting possible combinations of menu items within a budget

Using Java 8, I am trying to figure out an algorithm / proper solution to see how to store a List<String> with buyable items within a certain allocated budget.

Suppose, a Map<String, Double> which contains the following keys / values:

Map<String, Double> menu = new HashMap<>();

menu.put("Fruit", 2.15);
menu.put("Fries", 2.75);
menu.put("Salad", 3.35);
menu.put("Wings", 3.55);
menu.put("Mozzarella", 4.20);
menu.put("Plate", 5.80);

Considering a method with the following signature:

public static List<List<String>> getListOfBuyableItems(
        Map<String, Double> menu, double budget)

The following rules need to be enforced:

  • Budget = 4.30, then the ArrayList returned is:
    [["Fruit", "Fruit"]]
  • Budget = 5.50, then the ArrayList returned is:
    [["Fries", "Fries"], ["Fruit", "Salad"]]
  • Budget = 2.15, then the ArrayList returned is:

This is what I've come up with, but I can't seem to figure out how to fix this using recursion and / or a different approach:

public static List<List<String>> getBuyableItems(
        Map<String, Double> menu, double budget) {
    if (menu.isEmpty() || budget < 1) {
        return Collections.emptyList();

    List<List<String>> buyableItems = new ArrayList<>();
    double amount = budget;

    for (Map.Entry<String, Double> menuItem : menu.entrySet()) {
        System.out.println(menuItem.getKey() + " $" + menuItem.getValue());
        if (budget > menuItem.getValue()) {
            keepBuying(menu, budget);
            amount = budget - menuItem.getValue();
    return buyableItems;

public static void keepBuying(Map<String, Double> menu, double budget) {
    if (budget > 0.00) {
        for (Map.Entry<String, Double> menuItem : menu.entrySet()) {
            budget -= menuItem.getValue();

How can I solve this problem using recursion or a different solution?

I'm just curious on now to solve this using either:

  • Using for or while loops
  • Java 8 features: Streams & Lambda


  • Here is a solution that uses recursion.

    To make things easier, I have defined an Item class that stores the name and the price of an item. The price is expressed in cents to avoid rounding issues. The menu is a list of items.

    import java.util.*;
    public class Solver
        private ArrayList<Item> menu;
        private ArrayList<String[]> solutions;
        public static class Item
            public String name;
            public int price;
            public Item(String name, int price)
       = name;
                this.price = price;
        public Solver(ArrayList<Item> menu)
   = menu;
        public ArrayList<String[]> solve(int budget)
            solutions = new ArrayList<String[]>();
            solve(new ArrayList<Item>(), 0, budget);
            return solutions;
        private void solve(ArrayList<Item> items, int first, int budget)
                // We have found a solution, store it
                solutions.add( ->[]::new));
                // Search for an item that fits in the budget
                for(int i=first;i<menu.size();i++)
                    Item item = menu.get(i);
                        solve(items, i, budget-item.price);
        public static void main(String[] args)
            ArrayList<Item> menu = new ArrayList<Item>();
            menu.add(new Item("Fruit", 215));
            menu.add(new Item("Fries", 275));
            menu.add(new Item("Salad", 335));
            menu.add(new Item("Wings", 355));
            menu.add(new Item("Mozzarella", 420));
            menu.add(new Item("Plate", 580));
            Solver solver = new Solver(menu);
            ArrayList<String[]> solutions = solver.solve(550);
            for(int i=0;i<solutions.size();i++)
                System.out.println("Solution "+(i+1)+": "+Arrays.toString(solutions.get(i)));


    Solution 1: [Fruit, Salad]
    Solution 2: [Fries, Fries]