如何查找和为给定值K的非连续子数组？可用算法有哪些？

你描述的「无需连续、和等于K的子数组」本质是经典的子集和问题，属于01背包问题的衍生类型，回溯法不是必须使用的方案，也存在成熟的动态规划等其他解法，具体说明如下：

1. 回溯法的适用场景 #

回溯是可选方案之一，更适配以下需求：

• 需要输出所有满足和为K的子集
• 数组规模小（通常元素个数<20），不需要额外存储状态表
• 数组包含负数元素，不需要调整规则就能直接使用

简化的回溯实现伪代码参考：

def backtrack(index, current_sum, selected):
    if current_sum == K:
        result.append(selected.copy())
        return
    if index == len(nums) or current_sum > K:
        return
    # 选中当前元素
    selected.append(nums[index])
    backtrack(index + 1, current_sum + nums[index], selected)
    selected.pop()
    # 不选中当前元素
    backtrack(index + 1, current_sum, selected)

如果数组存在重复元素，可以先排序再剪枝，避免输出重复子集。

2. 动态规划的适配方案 #

动态规划完全可以解决该问题，分两种常见场景：

2.1 仅判断是否存在符合条件的子集 #

这是最基础的01背包变种，定义dp[j]表示是否可以凑出和为j的子集，状态转移规则为：
dp[j] = dp[j] or dp[j - nums[i]]
优化后时间复杂度为O(n*K)，空间复杂度为O(K)，当K数值不大（通常<1e4）时，效率远高于回溯法。

2.2 需要输出具体子集 #

在基础动态规划的基础上额外记录状态转移路径，得到dp表后反向回溯转移路径，就能提取出对应的元素集合。如果只需要输出任意一个符合条件的子集，该方案比暴力回溯效率高很多。

3. 其他可选解法 #

如果数组元素规模中等（20~40之间），还可以使用双向搜索方案：将数组拆成前后两半，分别枚举两半所有子集的和，再匹配两边和相加等于K的组合，时间复杂度可以降到O(2^{(n/2))，比纯回溯的O(2}n)性能提升明显。

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