Apple OA 面试真题解析：预算内苹果产品组合枚举（回溯 / 组合）

Problem 1: Given a budget of $3000 dollars to buy Apple products, create an algorithm to print all possible combinations of products you can buy.

Given the following product categories, each combination should contain one product from each category.

MacBooks:

• MacBook Air – $1249
• MacBook Pro 13 Inch – $1399
• MacBook Pro 15 Inch – $2299
• MacPro – $5999

iPads:

• iPad Pro – $1299
• iPad Air – $729
• iPad – $459

iPhone:

• iPhone 14 Pro – $1299
• iPhone 12 – $799
• iPhone 14 – $699
• iPhone 12 Pro Max – $1499

Apple Watch:

• Apple Watch Nike – $499
• Apple Watch Hermes – $1099
• Apple Watch Series 6 – $499

AirPods:

• AirPods Pro – $299
• AirPods – $149
• AirPods Max – $549

Print all valid combinations whose total cost is within the budget.

这道题本质上是一个“分组组合枚举”问题：需要从每个苹果产品类别中各选一个商品，并且总价不超过 3000 美元，输出所有满足条件的搭配。核心做法通常是回溯或多层嵌套枚举，在每一层选择当前类别的一个商品，累加价格并在超过预算时提前剪枝。由于题目要求每个组合必须覆盖所有类别，因此这是典型的组合搜索问题，重点在于正确组织类别顺序、控制总成本，以及在搜索过程中尽早过滤不可能的方案。