A Variant of the Knapsack Problem: Target Sum

labuladongOriginalAbout 4835 words

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
494. Target Sum	🟠

Prerequisites

Before reading this article, you should first learn:

Dynamic Programming Core Framework

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 = 3
Output: 5
Explanation: 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 = 1
Output: 1

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

The function signature is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

A Variant of the Knapsack Problem: Target Sum

494. 目标和 https://leetcode.cn/problems/target-sum

494. Target Sum https://leetcode.com/problems/target-sum

I. Backtracking Approach

2. Converting to a Dynamic Programming Approach

III. Knapsack Problem