Loading
Loading
A grocery app lets a shopper tick any combination of the items on a short list. To show instant totals, it precomputes the price of every possible basket.
Number the baskets with a bitmask: basket m contains item i exactly when bit i of m is 1. Given the item prices (some may be discounts, so negative), return a list of length 2ⁿ where entry m is the total price of basket m.
prices = [3, 5, -2]m = 000empty basket → 0m = 001item 0 → 3m = 010item 1 → 5m = 011basket 010 plus item 0 → 8m = 100item 2 → -2m = 101basket 100 plus item 0 → 1m = 110basket 100 plus item 1 → 3m = 111basket 110 plus item 0 → 6[0, 3, 5, 8, -2, 1, 3, 6]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Mask 5 = 101 picks items 0 and 2, so its total is 3 + (-2) = 1.
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(2ⁿ) time · O(2ⁿ) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Example 2
Masks 1 and 2 pick different items, even though their prices match.