# 目标和问题：背包问题的变体

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

494. Target Sum | 🟠 |

In previous articles, we often mentioned that backtracking algorithms are somewhat similar to recursive algorithms. If you can't figure out the state transition equation for a problem, trying to solve it using a backtracking algorithm as a brute-force approach can be a smart strategy. It's better than not being able to write any solution at all.

So, what is the relationship between backtracking algorithms and dynamic programming? Both involve recursion, and their algorithm templates look quite similar, as they both involve making "choices." They really do resemble a parent-child relationship.

So, what are the specific differences between them? Is it possible to transform one into the other between backtracking algorithms and dynamic programming?

Today, we will use LeetCode problem #494 "Target Sum" to compare backtracking algorithms and dynamic programming in detail. The problem is as follows:

**494. Target Sum** | 力扣 | LeetCode |

You are given an integer array `nums`

and an integer `target`

.

You want to build an **expression** out of nums by adding one of the symbols `'+'`

and `'-'`

before each integer in nums and then concatenate all the integers.

- For example, if
`nums = [2, 1]`

, you can add a`'+'`

before`2`

and a`'-'`

before`1`

and concatenate them to build the expression`"+2-1"`

.

Return the number of different **expressions** that you can build, which evaluates to `target`

.

**Example 1:**

Input:nums = [1,1,1,1,1], target = 3Output:5Explanation:There are 5 ways to assign symbols to make the sum of nums be target 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

**Example 2:**

Input:nums = [1], target = 1Output:1

**Constraints:**

`1 <= nums.length <= 20`

`0 <= nums[i] <= 1000`

`0 <= sum(nums[i]) <= 1000`

`-1000 <= target <= 1000`

The function signature is as follows:

`int findTargetSumWays(int[] nums, int target);`

`int findTargetSumWays(vector<int>& nums, int target);`

`def findTargetSumWays(nums: List[int], target: int) -> int:`

`func findTargetSumWays(nums []int, target int) int {`

`var findTargetSumWays = function(nums, target) {};`

## I. Backtracking Approach

Actually, when I first saw this problem, it took me just two minutes to come up with a backtracking solution.

The core of any algorithm is exhaustive enumeration, and backtracking is a brute-force enumeration algorithm. The previous article Backtracking Algorithm Framework outlined the framework for backtracking:

```
def backtrack(path, choices):
if meets_end_condition:
result.add(path)
return
for choice in choices:
make_choice
backtrack(path, choices)
undo_choice
```

The key is to understand what constitutes a "choice". For this problem, isn't the "choice" obvious? **For each number nums[i], we can choose to assign either a positive sign + or a negative sign -**. Then, using the backtracking template, we can enumerate all possible outcomes and count how many combinations can sum up to the

`target`

.The pseudocode approach is as follows: