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.
Asked at:
Apple
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early June, 2026
Apple
Mid-level
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.