深搜练习(目标和)(6)

一.题目

494. 目标和 - 力扣（LeetCode）

二.思路讲解

2.1 思路讲解

本题要求为数组nums中的每个整数前面添加+或-，使得整个表达式的计算结果等于target，并返回不同的表达式数目。这本质上是一个多阶段决策问题：对于每个元素，我们都有两种选择（加或减），我们需要枚举所有可能的符号组合，并统计和为target的个数。

我们可以采用深度优先搜索（DFS）的回溯框架来解决。递归函数dfs(pos, sum)表示当前已经处理到下标pos，且已累积的和为sum。当pos == n时，检查sum == target，若相等则计数加一。否则，对于当前元素nums[pos]，我们有两种递归分支：

• 选择加号：dfs(pos+1, sum + nums[pos])

• 选择减号：dfs(pos+1, sum - nums[pos])

三.代码演示

class Solution { public: int ret; int findTargetSumWays(vector<int>& nums, int target) { dfs(nums,target,0,0); return ret; } void dfs(vector<int>& nums,int target,int path,int pos) { if(pos == nums.size()) { if(path == target) { ret++; return; } return; } dfs(nums,target,path + nums[pos],pos+1); dfs(nums,target,path - nums[pos],pos+1); } };

四.代码讲解

一、全局变量设计

为了实现回溯统计，我们定义一个成员变量：

• ret：整型，用于累计满足条件的表达式数目，初始为 0。

这里没有使用path数组来存储具体表达式，因为我们只关心结果计数，不关心具体符号序列。状态通过递归参数传递，不需要手动回溯恢复。

二、主函数findTargetSumWays

主函数接收数组nums和目标值target，调用递归函数dfs(nums, target, 0, 0)开始深度优先搜索，最后返回ret。参数含义：

• path：当前已累积的和，初始为 0。

• pos：当前处理到数组的第pos个元素，初始为 0。

三、递归函数dfs

递归函数dfs(nums, target, path, pos)的含义是：已经处理了前pos个元素，当前累积和为path，接下来需要为第pos个元素选择符号。执行流程如下：

1. 递归终止条件

当pos == nums.size()时，说明所有元素都已处理完毕，得到一个完整的表达式。此时检查累积和path是否等于target，若相等，则将ret加 1。然后返回（无论是否相等，都结束此分支）。

2. 递归分支（两种选择）

对于当前元素nums[pos]，我们有两种符号选择：

• 加号：调用dfs(nums, target, path + nums[pos], pos + 1)，表示将当前元素加入和。

• 减号：调用dfs(nums, target, path - nums[pos], pos + 1)，表示将当前元素减去。

这两种选择分别探索了不同的符号组合，最终会覆盖所有2^n种可能。

四、回溯与恢复现场

由于path是通过值传递的方式传入递归函数，而不是使用全局变量，因此不需要手动恢复现场。每一层递归都有自己的path副本，互不干扰。这种设计简化了回溯的复杂度，但会带来额外的拷贝开销（在此题中开销很小）。