LeetCode 补充题 117. 目标和非空子序列的枚举
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 78. 子集
:::
给你一个整数数组
nums和一个整数target，返回所有元素和等于target的非空子序列。子序列可以不连续，但必须保持原下标的相对顺序。不同的下标选择分别计入结果，即使得到的数值序列相同，也需要分别保留。结果顺序不限。
示例 1：
输入：
nums = [5,5,10,2,3], target = 15
输出：[[5,10],[5,10],[10,2,3],[5,5,2,3]]
解释： 两个[5,10]使用了不同位置的5；[5,5,2,3]跳过10，因此是子序列而非连续子数组。
示例 2：
输入：
nums = [0,0], target = 0
输出：[[0],[0],[0,0]]
解释： 按下标区分三个非空选择，空集不输出。
提示：
- 元素允许为负数。
- 和使用
64位整数。 - 结果顺序不限。
- 输出数量最坏为指数级，适合能够完整枚举答案的输入规模。
题意分析
子序列只要求下标递增，不要求连续，也不能重排。相同数值来自不同下标时仍是不同方案，因此每个下标都要独立决定选或不选，不能按数值去重。
解法：按下标选与不选的回溯
核心思路
[!blue]
dfs(index,sum)表示前index个位置已经决定完毕，path保存所选值且顺序与原数组一致，sum是它们的 64 位累计和。当前下标先走不选分支，再将该值加入路径走选择分支；返回后移除末项，恢复调用前状态。每一组下标选择都对应唯一一条分支路径，全部递归到数组末尾后，筛选路径非空且
sum == target的叶子。保存时复制路径，避免后续回溯修改已经收集的结果。元素可以为负数或 0，所以当前和超过目标仍可能被后续负数抵消，当前和达到目标也可能继续产生其他方案。不能据此提前结束，也不能把
target == 0时的空路径作为答案。
解题步骤
- 对每个下标分别递归不选与选择两种分支。
- 到数组末尾才根据路径非空和目标和判定保存副本。
- 选择分支返回后移除最后一个元素，恢复路径。
代码实现
class Solution {
public List<List<Integer>> sumSubsequences(int[] nums, long target) {
List<List<Integer>> out = new ArrayList<>();
dfs(nums, 0, 0, target, new ArrayList<>(), out);
return out;
}
private void dfs(
int[] nums,
int index,
long sum,
long target,
List<Integer> path,
List<List<Integer>> out) {
if (index == nums.length) {
if (!path.isEmpty() && sum == target) {
out.add(new ArrayList<>(path));
}
return;
}
dfs(nums, index + 1, sum, target, path, out);
path.add(nums[index]);
dfs(nums, index + 1, sum + nums[index], target, path, out);
path.remove(path.size() - 1);
}
}
func sumSubsequences(nums []int, target int64) [][]int {
out := [][]int{}
path := []int{}
var dfs func(int, int64)
dfs = func(index int, sum int64) {
if index == len(nums) {
if len(path) > 0 && sum == target {
out = append(out, append([]int(nil), path...))
}
return
}
dfs(index+1, sum)
path = append(path, nums[index])
dfs(index+1, sum+int64(nums[index]))
path = path[:len(path)-1]
}
dfs(0, 0)
return out
}
复杂度分析
- 时间复杂度：$O(2^n+R)$。
- 空间复杂度：辅助空间 $O(n)$，结果空间 $O(R)$；R 为全部输出序列的元素总数。
关键点总结
[!green]
元素可负可零，当前和超过目标不能剪枝，提前等于目标也不能停止，否则会漏掉后续补零或抵消的方案。
易错点总结
[!yellow]
不能排序输入或用集合去重，否则会改变原顺序或丢失不同下标的方案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 78. 子集 | 中等 | 同样按下标选或不选，本题仅输出目标和非空子序列，并保持原下标顺序。 |
| 39. 组合总和 | 中等 | 同样枚举目标和方案，原题正整数可重复使用，本题每个下标只能用一次且可能有负数，不能照搬剪枝。 |