Find every distinct triplet of prices summing to a total
A gift shop sells a “pick any 3” bundle: customers choose three items whose prices add up to exactly the value of their gift card, so nothing is left over. Given the catalogue’s prices and a card value, list every distinct bundle the customer can choose.
Implement findTriplets(prices, total).
findTriplets(prices, total) // => number[][]
prices is an array of integers (zero and negative values, such as discount vouchers, are allowed). total is an integer.prices whose values sum to total. A value can appear more than once in a bundle only if it appears that many times in prices.5 are interchangeable. Return each combination of values once.[] when no bundle exists, including when there are fewer than three prices.prices.prices can have up to 400 items. Checking every triple of positions is cubic and will time out.findTriplets([5, 10, 15, 20, 25], 45);
// => [[5, 15, 25], [10, 15, 20]]
findTriplets([30, 10, 20, 0, 40, 50], 60);
// => [[0, 10, 50], [0, 20, 40], [10, 20, 30]]
findTriplets([5, 5, 5, 10, 10], 20);
// => [[5, 5, 10]] (counted once, even though many position triples match)
findTriplets([4, 8, 12], 12);
// => [] (4 + 4 + 4 needs three 4s)
findTriplets([-10, 0, 10, 20, -20], 0);
// => [[-20, 0, 20], [-10, 0, 10]]
findTriplets([10, 20], 30);
// => []