挑选宝石
2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷
华为OD机试双机位C卷真题目录点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（OD上机考试双机位C卷）
题目描述
游乐园有一款互动游戏，游戏开始时会提供n个宝石，每个宝石都一个属性值a1,a2,…an.玩家在游戏前可以挑选x颗宝石，将这些宝石的属性值相乘组成玩家的属性值。游戏玩家需要y点属性值，请帮助游戏玩家计算有多少种计算方式。
输入描述
第一行：三个整数n,x,y
-
第一个整数n(0 < n <20)表示宝石总数量。
-
第二个整数x(0<x <=n)，表示可以选择宝石个数
-
第三个整数y，表示通过游戏需要的属性值
第二行：n个整数，a1,a2,…an(-100 < ai < 100)，表示每个宝石的属性值。
输出描述
输出一个整数，表示玩家可以通过游戏的挑选方式的数量。
示例1
输入
4 2 8
2 -3 4 5输出
3说明
解题思路
这是一个经典的组合问题，可以通过 深度优先搜索 (DFS) / 回溯法 来解决。
由于宝石数量 $n$ 较小（ $n < 20$ ），我们可以遍历所有可能的组合，找出其中选取 $x$ 个宝石且乘积等于 $y$ 的方案数量。