题目描述给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个表达式例如nums [2, 1]可以在2之前添加在1之前添加-然后串联起来得到表达式2-1。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。示例 1输入nums [1,1,1,1,1], target 3输出5解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3示例 2输入nums [1], target 1输出1解题思路方法一回溯DFS思路对于每个数字有两种选择加或加-。递归到最后一个数字时判断和是否等于target是则计数 1代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { int count 0; backtrack(nums, target, 0, 0, count); return count; } private: void backtrack(vectorint nums, int target, int index, int sum, int count) { if (index nums.size()) { if (sum target) count; return; } // 选择 backtrack(nums, target, index 1, sum nums[index], count); // 选择 - backtrack(nums, target, index 1, sum - nums[index], count); } };复杂度分析维度复杂度说明时间复杂度O(2^n)每个数字两种选择空间复杂度O(n)递归栈深度缺点数据量大时超时。方法二动态规划转化为 01 背包核心转化设所有数字的和为sum加的数字和为P加-的数字和为N。P N sum P - N target两式相加2P sum target即P (sum target) / 2问题转化为从nums中选一些数字使它们的和等于P求方案数。这就是 01 背包问题代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { int sum 0; for (int num : nums) sum num; // 无法整除或目标绝对值超过总和 if ((sum target) % 2 ! 0 || abs(target) sum) return 0; int P (sum target) / 2; // dp[j] 和为 j 的方案数 vectorint dp(P 1, 0); dp[0] 1; for (int num : nums) { for (int j P; j num; j--) { dp[j] dp[j - num]; } } return dp[P]; } };具体过程示例nums [1,1,1,1,1],target 3sum 5 P (5 3) / 2 4 问题转化为从 [1,1,1,1,1] 中选数字和为 4 的方案数 dp[0] 1 遍历每个 1: dp[1] dp[0] → dp[1] 1 dp[2] dp[1] → dp[2] 1 dp[3] dp[2] → dp[3] 1 dp[4] dp[3] → dp[4] 1 遍历第二个 1: dp[1] dp[0] → dp[1] 2 dp[2] dp[1] → dp[2] 3 dp[3] dp[2] → dp[3] 4 dp[4] dp[3] → dp[4] 5 ...最终 dp[4] 5 ✅复杂度分析维度复杂度说明时间复杂度O(n × P)n 个数字P 是目标和空间复杂度O(P)dp 数组方法三记忆化搜索思路在回溯的基础上用哈希表记录(index, sum)的结果避免重复计算。代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { unordered_mapstring, int memo; return dfs(nums, target, 0, 0, memo); } private: int dfs(vectorint nums, int target, int index, int sum, unordered_mapstring, int memo) { if (index nums.size()) { return sum target ? 1 : 0; } string key to_string(index) , to_string(sum); if (memo.count(key)) return memo[key]; int count dfs(nums, target, index 1, sum nums[index], memo) dfs(nums, target, index 1, sum - nums[index], memo); memo[key] count; return count; } };复杂度分析维度复杂度说明时间复杂度O(n × sum)每个 (index, sum) 只算一次空间复杂度O(n × sum)哈希表三种方法对比方法时间复杂度空间复杂度推荐度回溯O(2^n)O(n)⭐⭐动态规划01背包O(n × P)O(P)⭐⭐⭐⭐⭐记忆化搜索O(n × sum)O(n × sum)⭐⭐⭐⭐总结要点说明核心思想转化为 01 背包选一些数字和为 P关键公式P (sum target) / 2时间复杂度O(n × P)空间复杂度O(P) 【回溯-7】494.目标和
题目描述给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个表达式例如nums [2, 1]可以在2之前添加在1之前添加-然后串联起来得到表达式2-1。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。示例 1输入nums [1,1,1,1,1], target 3输出5解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3示例 2输入nums [1], target 1输出1解题思路方法一回溯DFS思路对于每个数字有两种选择加或加-。递归到最后一个数字时判断和是否等于target是则计数 1代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { int count 0; backtrack(nums, target, 0, 0, count); return count; } private: void backtrack(vectorint nums, int target, int index, int sum, int count) { if (index nums.size()) { if (sum target) count; return; } // 选择 backtrack(nums, target, index 1, sum nums[index], count); // 选择 - backtrack(nums, target, index 1, sum - nums[index], count); } };复杂度分析维度复杂度说明时间复杂度O(2^n)每个数字两种选择空间复杂度O(n)递归栈深度缺点数据量大时超时。方法二动态规划转化为 01 背包核心转化设所有数字的和为sum加的数字和为P加-的数字和为N。P N sum P - N target两式相加2P sum target即P (sum target) / 2问题转化为从nums中选一些数字使它们的和等于P求方案数。这就是 01 背包问题代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { int sum 0; for (int num : nums) sum num; // 无法整除或目标绝对值超过总和 if ((sum target) % 2 ! 0 || abs(target) sum) return 0; int P (sum target) / 2; // dp[j] 和为 j 的方案数 vectorint dp(P 1, 0); dp[0] 1; for (int num : nums) { for (int j P; j num; j--) { dp[j] dp[j - num]; } } return dp[P]; } };具体过程示例nums [1,1,1,1,1],target 3sum 5 P (5 3) / 2 4 问题转化为从 [1,1,1,1,1] 中选数字和为 4 的方案数 dp[0] 1 遍历每个 1: dp[1] dp[0] → dp[1] 1 dp[2] dp[1] → dp[2] 1 dp[3] dp[2] → dp[3] 1 dp[4] dp[3] → dp[4] 1 遍历第二个 1: dp[1] dp[0] → dp[1] 2 dp[2] dp[1] → dp[2] 3 dp[3] dp[2] → dp[3] 4 dp[4] dp[3] → dp[4] 5 ...最终 dp[4] 5 ✅复杂度分析维度复杂度说明时间复杂度O(n × P)n 个数字P 是目标和空间复杂度O(P)dp 数组方法三记忆化搜索思路在回溯的基础上用哈希表记录(index, sum)的结果避免重复计算。代码实现class Solution { public: int findTargetSumWays(vectorint nums, int target) { unordered_mapstring, int memo; return dfs(nums, target, 0, 0, memo); } private: int dfs(vectorint nums, int target, int index, int sum, unordered_mapstring, int memo) { if (index nums.size()) { return sum target ? 1 : 0; } string key to_string(index) , to_string(sum); if (memo.count(key)) return memo[key]; int count dfs(nums, target, index 1, sum nums[index], memo) dfs(nums, target, index 1, sum - nums[index], memo); memo[key] count; return count; } };复杂度分析维度复杂度说明时间复杂度O(n × sum)每个 (index, sum) 只算一次空间复杂度O(n × sum)哈希表三种方法对比方法时间复杂度空间复杂度推荐度回溯O(2^n)O(n)⭐⭐动态规划01背包O(n × P)O(P)⭐⭐⭐⭐⭐记忆化搜索O(n × sum)O(n × sum)⭐⭐⭐⭐总结要点说明核心思想转化为 01 背包选一些数字和为 P关键公式P (sum target) / 2时间复杂度O(n × P)空间复杂度O(P)