部分和问题 (难度：中等) 竞技编程-提高思维

题目描述 给定整数 a1、a2、…、an，判断是否可以从中选出若干数，使它们的和恰好为 k。

输入格式

• 第一行输入一个整数 n (1 ≤ n ≤ 20)，表示数组的大小。
• 第二行输入 n 个整数 a1, a2, …, an (-10 ≤ ai ≤ 10)，表示数组的元素。
• 第三行输入一个整数 k (-10 ≤ k ≤ 100)，表示目标和。

输出格式 如果可以从数组中选出若干个数使得它们的和恰好为 k，输出 "Yes"，否则输出 "No"。

示例

输入示例 1：

4  
1 2 4 7  
13

输出示例 1：

Yes

解释：选择 2 + 4 + 7 = 13，满足条件。

输入示例 2：

5  
1 2 3 4 5  
11

输出示例 2：

Yes

解释：选择 2 + 3 + 4 + 5 = 11，满足条件。

输入示例 3：

3  
-1 2 3  
6

输出示例 3：

No

解释：没有任何组合的和等于 6。

时间复杂度分析 由于数组的大小 n 最大为 20，因此可以使用回溯算法（暴力穷举所有组合）来解决此问题。 对于每个元素，可以选择或不选择，因此总共有 2^n 种组合方式。 因此，时间复杂度为 O(2^n)，其中 n 是数组的大小，最大值为 20，所以 2^n 的最大值为 1048576，完全可以接受。