1850 - 和为T 题目描述 从一个大小为 � n 的整数集中选取一些元素，使得它们的和等于给定的值 � T。 每个元素限选一次，不能一个都不选。 输入 第一行一个正整数 � n，表示整数集内元素的个数。 第二行 � n 个整数，用空格隔开。 第三行一个整数 � T，表示要达到的和。 输出 输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。 若有多组解，优先输出不包含第 � n 个整数的；若都包含或都不包含，优先输出不包含第 � − 1 n−1 个整数的，依次类推。 最后一行输出总方案数。 样例 输入复制 5 -7 -3 -2 5 9 0 输出复制 -3 -2 5 -7 -2 9 2 说明 【来源】 蓝桥杯算法训练 数据规模和约定 1 ≤ � ≤ 22 1≤n≤22， � ≤ � � � � � � � � � � T≤maxlongint，集合中任意元素的和都不超过 long long 的范围。 来源 蓝桥杯 深搜 标签 蓝桥杯深搜排列组合

### 题目解析：蓝桥杯 - 和为 T #### 描述 该问题是经典的“子集和”问题的一种变种。我们需要在一个长度为 `n` 的整数数组中选择某些元素，使它们的和恰好等于目标值 `T`。每个元素只能被选一次，并且至少需要选择一个元素。 此外，输出结果还需要满足特定的排序规则： - 如果有多组解，则优先输出不包含最后一个元素的； - 若所有解都包含或都不包含某个元素，则继续考虑前一个元素，以此类推。 最后，程序还需输出总的方案数。 #### 输入格式 1. 第一行是一个正整数 `n (1 ≤ n ≤ 22)` 表示整数的数量。 2. 第二行是这 `n` 个整数，用空格分隔。 3. 第三行是一个整数 `T (-maxlongint ≤ T ≤ maxlongint)`, 即期望得到的目标和。 #### 输出格式 1. 每一行代表一种符合条件的选择方案，按上述规则从小到大排列。 2. 最后一行给出所有的合法方案总数。 #### 示例分析 ```plaintext 输入: 5 -7 -3 -2 5 9 0 输出: -3 -2 5 -7 -2 9 2 ``` 在这个例子中，两个不同的组合可以达到零 (`{-3, -2, 5}` 和 `{−7, −2, 9}`)，所以这两个组合都被打印出来并按照规定顺序显示。 #### 算法思路 考虑到本题的数据规模较小(`n <= 22`)，我们可以采用深度优先搜索(DFS)来解决问题。DFS非常适合解决此类枚举型的问题，在遍历过程中通过回溯的方式不断尝试新的可能性直到找到所有的可行解为止。 **步骤** 1. 定义递归函数 dfs(index, current_sum)，其中 index 表示当前正在处理的是第几个数字，current_sum 则记录已经取得的所有数值之和。 2. 当 index 达到了数组末尾时检查是否找到了合适的解决方案： - 如果刚好凑齐了所需的 sum(T), 将这个路径保存下来作为其中一个答案。 - 否则就结束本次查找过程返回上一层级。 3. 对于每一个未访问过的节点有两种情况可以选择——取它或者不取它。因此对于每一个新位置我们都将分别调用两次 DFS 函数来进行探索。 4. 在每次成功构建出完整序列之后都要记得更新计数器以统计总共得到了多少条有效路线。 为了保证最终的结果能够依照题目要求有序地呈现，可以在收集完全部的答案后再做一次稳定排序操作。 下面是基于以上思想的一个简单 Python 实现： ```python def solve(n, nums, target): results = [] def dfs(start_index=0, path=[], curr_sum=0): if start_index == len(nums): # base case: reached end of list if curr_sum == target and path != []: nonlocal results results.append(path.copy()) return for i in range(len(results)): if sorted(results[i]) > sorted(path + [nums[start_index]]): break else: dfs(start_index+1, path+[nums[start_index]], curr_sum+nums[start_index]) dfs(start_index+1, path, curr_sum) dfs() results.sort(key=lambda x:(tuple(x[::-1]))) result_count = len(results) print(*('\t'.join(map(str,x)) for x in results ), sep='\n') print(result_count) if __name__ == '__main__': import sys input = lambda :sys.stdin.readline().strip() n = int(input()) nums = list(map(int,input().split())) target = int(input()) solve(n, nums, target) ``` 注意此段代码仅为示范用途，实际应用可能会因为效率等原因调整细节部分。