#11934. 抽取纸片

抽取纸片

问题 :抽取纸片

(难度:中等) 竞技编程-提高思维

题目描述 你的朋友提议玩一个游戏:将写有数字的几个纸片放入口袋中,你可以从口袋中抽取4次纸片,每次记下纸片上的数字后都将其放回口袋中。如果这4个数字的和是 mm,就是你赢,否则就是你的朋友赢。你挑战了好几回,结果一次也没赢过,于是怒而撕破口袋,取出所有纸片,检查自己是否真的有赢的可能性。

请你编写一个程序,判断当纸片上所写的数字是 h_1,h_2,,h_nh\_1, h\_2, \dots, h\_n 时,是否存在抽取4次和为 m 的方案。如果存在,输出 Yes;否则,输出 No

输入格式

  • 第一行,整数 nn 表示纸片的数量。
  • 第二行,整数 mm 表示目标和。
  • 第三行,整数数组 k={k_1,k_2,,k_n}k = \{k\_1, k\_2, \dots, k\_n\} 表示每张纸片上写的数字。

输出格式

  • 如果存在一组四个数字的和为 mm,输出 Yes,否则输出 No

示例 1 输入

3
10
1 3 5

输出

Yes

(例如4次抽取的结果是1、1、3、5,和为10)

示例 2 输入

3
9
1 3 5

输出

No

(不存在和为9的抽取方案)

时间复杂度分析 由于你需要判断是否存在4个数字和为 mm,可以通过枚举4个数字的组合来解决。最坏情况下需要枚举 O(n4)O(n^4) 次,这对于 n50n≤50 是可以接受的。