Find All Combinations of Bag Sizes That Sum to a Target Capacity
Given a list of chocolate bag sizes (each size may be used any number of times) and a target capacity n, find all unique combinations of bags whose sizes sum exactly to n. For example, given bag sizes [200, 100, 300] and target 500, return all combinations such as [200, 200, 100], [200, 300], [100, 100, 300], [100, 100, 100, 100, 100], etc. The core challenge is a backtracking/DFS search with deduplication to enumerate all valid combinations without permutation duplicates.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early June, 2026
Given different types of chocolates. Find all possible combinations of chocolate bags that can fit in a big bag with a capacity n. Example: Bag of Hersheys: capacity=200 Bag of MNM: capacity = 100 Bag of Godiva: capacity= 300 Big Bag Capacity: 500 Possible combos: HHM, HG, GMM, MMMMM.
Hello Interview Premium
Your account is free and you can post anonymously if you choose.