如何从K₁至K_N整数集合各选元素，使其和等于目标值C（非暴力解法）

给定N个已排序的非负整数集合K₁~K_N，目标是从每个集合选一个元素，使其和等于C，找出至少一种可行方案，以下是几种非暴力的实现思路：

一、分治法（Divide & Conquer） #

• 将集合分成前后两组，分别计算每组所有可能的元素组合和，同时记录每个和对应的选取路径
• 对第一组的和集合排序，遍历第二组的每个和s，检查C - s是否存在于第一组的和集合中
• 一旦找到匹配的两个和，合并对应的两组路径，即可得到完整可行方案
• 优化点：计算组合和时，若当前累计和已超过C，直接停止该分支计算（所有元素非负，后续加元素只会让和更大）

二、带剪枝的回溯法 #

• 利用集合已排序的特性做有序回溯：
  1. 按集合顺序依次选元素，每选一个就更新剩余目标值（剩余目标 = C - 已选元素和）
  2. 对当前集合，只遍历小于等于剩余目标的元素（后续集合还要选非负元素，当前元素不能超过剩余目标）
  3. 若当前集合的最小元素已大于剩余目标，直接回溯（不可能找到可行解）
  4. 一旦找到元素和等于C，立即返回结果，无需继续遍历
• 关键优化：集合已排序，遍历元素从前往后，找到可行解就终止，避免无效递归

三、动态规划+路径记录 #

• 构建动态规划结构dp，其中dp[i][s]表示前i个集合能否凑出和为s，同时记录凑出s时第i个集合选取的元素
• 初始化：dp[0][0] = True，表示0个集合凑和为0可行
• 状态转移：对第i个集合的每个元素k，遍历所有dp[i-1][s]为True的s，若s + k <= C，则标记dp[i][s + k] = True，并记录该路径（选取k）
• 路径回溯：若dp[N][C]为True，从C倒推：
  1. 从第N个集合找元素k，使得dp[N-1][C - k]为True
  2. 将k加入结果列表，更新C为C - k，继续处理第N-1个集合
• 优化点：用一维滚动数组优化空间，只保留前一个集合的可行和集合，减少内存占用

四、双指针变种（适合N较小的场景，如N=2或N=3） #

• N=2时：直接用双指针，左指针从K₁头部开始，右指针从K₂尾部开始：
  • 和小于C：左指针右移
  • 和大于C：右指针左移
  • 和等于C：返回当前元素对
• N=3时：先计算K₁和K₂的所有可能和（带路径）并排序，对K₃的每个元素k，用双指针在K₁+K₂的和集合中找C - k，找到后合并路径

内容的提问来源于stack exchange，提问作者user91