Problem

Given a menu represented as a map from item name to price and a target budget, return all combinations of menu item names whose total price equals the budget. Items can be chosen multiple times unless the menu semantics restrict repetitions (this version allows repeats — each menu item is unlimited).

Prices should ideally be treated as integers (for example, cents) to avoid floating-point rounding issues.

Example 1

1
2
3
4
5

Input:
menu = {"Fruit": 215, "Fries": 275, "Salad": 335, "Wings": 355, "Mozzarella": 420, "Plate": 580}
budget = 430

Output: [["Fruit", "Fruit"]]

Example 2

1
2
3
4

Input: {"Fruit": 215, "Fries": 275, "Salad": 335, "Wings": 355, "Mozzarella": 420, "Plate": 580}
budget = 550

Output: [["Fries", "Fries"], ["Fruit", "Salad"]]

Notes

  • Treat prices as integer cents (e.g., 2.15 -> 215) to avoid floating-point comparisons.
  • This problem is a direct variant of the Combination Sum problem (LeetCode 39 / “Combination Sum”).
Similar Problems

Solution

The standard solution is backtracking (depth-first search) analogous to Combination Sum: convert the map into a list of (name, price) pairs sorted by price, then explore combinations by iterating choices and recursing with decreased remaining budget.

Method 1 — Backtracking

Intuition

At each step pick a menu item (possibly the same as prior picks) and subtract its price from the remaining budget. If the remaining budget becomes 0, the current combination is valid. If it becomes negative, backtrack. Sorting items by price allows early pruning.

Approach

  • Convert menu map to a list items of (name, price) pairs and sort by price.
  • If any price is greater than budget and all remaining prices are >= it, you can skip further choices.
  • Maintain curr (list of selected names) and ans (list of combinations).
  • Define dfs(idx, rem):
    • If rem == 0 append a copy of curr to ans and return.
    • If rem < 0 return.
    • For i from idx to len(items)-1:
      • Append items[i].name to curr and call dfs(i, rem - items[i].price) (allow reuse of same item).
      • Pop last from curr.
  • Return ans.

Edge cases: empty menu or non-positive budget -> return [].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
  vector<vector<string>> menuCombinations(vector<pair<string,int>> items, int budget) {
    sort(items.begin(), items.end(), [](auto &a, auto &b){ return a.second < b.second; });
    vector<string> curr;
    vector<vector<string>> ans;
    function<void(int,int)> dfs = [&](int idx, int rem) {
      if (rem == 0) { ans.push_back(curr); return; }
      if (rem < 0) return;
      for (int i = idx; i < (int)items.size(); ++i) {
        if (items[i].second > rem) break;
        curr.push_back(items[i].first);
        dfs(i, rem - items[i].second);
        curr.pop_back();
      }
    };
    dfs(0, budget);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package main

func menuCombinations(items [][2]interface{}, budget int) [][]string {
	// items: slice of [name, price]
	// Convert and sort externally if needed; here assume reasonable ordering
	var ans [][]string
	curr := make([]string, 0)
	var dfs func(int, int)
	dfs = func(idx, rem int) {
		if rem == 0 {
			tmp := make([]string, len(curr))
			copy(tmp, curr)
			ans = append(ans, tmp)
			return
		}
		if rem < 0 { return }
		for i := idx; i < len(items); i++ {
			name := items[i][0].(string)
			price := items[i][1].(int)
			if price > rem { continue }
			curr = append(curr, name)
			dfs(i, rem-price)
			curr = curr[:len(curr)-1]
		}
	}
	dfs(0, budget)
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.*;

class Solution {
  static class Item {
    String name;
    int price;
    Item(String n, int p) { name = n; price = p; }
  }

  public List<List<String>> menuCombinations(List<Item> items, int budget) {
    items.sort(Comparator.comparingInt(a -> a.price));
    List<String> curr = new ArrayList<>();
    List<List<String>> ans = new ArrayList<>();
    dfs(items, 0, budget, curr, ans);
    return ans;
  }

  private void dfs(List<Item> items, int idx, int rem, List<String> curr, List<List<String>> ans) {
    if (rem == 0) { ans.add(new ArrayList<>(curr)); return; }
    if (rem < 0) return;
    for (int i = idx; i < items.size(); i++) {
      Item it = items.get(i);
      if (it.price > rem) break;
      curr.add(it.name);
      dfs(items, i, rem - it.price, curr, ans);
      curr.remove(curr.size() - 1);
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  data class Item(val name: String, val price: Int)
  fun menuCombinations(items: List<Item>, budget: Int): List<List<String>> {
    val sorted = items.sortedBy { it.price }
    val ans = mutableListOf<List<String>>()
    val curr = mutableListOf<String>()
    fun dfs(idx: Int, rem: Int) {
      if (rem == 0) { ans.add(curr.toList()); return }
      if (rem < 0) return
      for (i in idx until sorted.size) {
        val it = sorted[i]
        if (it.price > rem) break
        curr.add(it.name)
        dfs(i, rem - it.price)
        curr.removeAt(curr.lastIndex)
      }
    }
    dfs(0, budget)
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def menu_combinations(self, items: list[tuple[str,int]], budget: int) -> list[list[str]]:
        items.sort(key=lambda x: x[1])
        m = len(items)
        ans: list[list[str]] = []
        curr: list[str] = []

        def dfs(idx: int, rem: int) -> None:
            if rem == 0:
                ans.append(curr.copy())
                return
            if rem < 0:
                return
            for i in range(idx, m):
                name, price = items[i]
                if price > rem:
                    break
                curr.append(name)
                dfs(i, rem - price)
                curr.pop()

        dfs(0, budget)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

pub struct Solution;
impl Solution {
    pub fn menu_combinations(mut items: Vec<(String, i32)>, budget: i32) -> Vec<Vec<String>> {
        items.sort_by_key(|x| x.1);
        let m = items.len();
        let mut ans: Vec<Vec<String>> = Vec::new();
        let mut curr: Vec<String> = Vec::new();
        fn dfs(items: &Vec<(String,i32)>, idx: usize, rem: i32, curr: &mut Vec<String>, ans: &mut Vec<Vec<String>>) {
            if rem == 0 { ans.push(curr.clone()); return }
            if rem < 0 { return }
            for i in idx..items.len() {
                let (ref name, price) = &items[i];
                if *price > rem { break }
                curr.push(name.clone());
                dfs(items, i, rem - *price, curr, ans);
                curr.pop();
            }
        }
        dfs(&items, 0, budget, &mut curr, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

export class Solution {
  menuCombinations(items: Array<[string, number]>, budget: number): string[][] {
    items.sort((a,b) => a[1] - b[1])
    const ans: string[][] = []
    const curr: string[] = []
    function dfs(idx: number, rem: number) {
      if (rem === 0) { ans.push(curr.slice()); return }
      if (rem < 0) return
      for (let i = idx; i < items.length; i++) {
        const [name, price] = items[i]
        if (price > rem) break
        curr.push(name)
        dfs(i, rem - price)
        curr.pop()
      }
    }
    dfs(0, budget)
    return ans
  }
}

Complexity

  • ⏰ Time complexity: O(m * Π_{i=0..m-1} s_i) where m is the number of distinct menu items and s_i is branching due to repeated choices — more informally, it’s proportional to the number of valid and explored combinations; sorting adds O(m log m).
  • 🧺 Space complexity: O(k * L) to store output where k is number of combinations and L average length; auxiliary recursion stack O(m).