A Variant of the Knapsack Problem: Target Sum

labuladongOriginalAbout 4830 words

This article will resolve

LeetCode	Difficulty
494. Target Sum	🟠

Prerequisites

Before reading this article, you should first learn:

Core Framework of Dynamic Programming

We often mention that backtracking algorithms are somewhat similar to recursive algorithms. If you really can't work out the state transition equation for a problem, trying to solve it with a brute-force backtracking algorithm is a clever strategy—it’s better than having no solution at all.

So, what exactly is the relationship between backtracking algorithms and dynamic programming? Both involve recursion, and their algorithm templates seem quite similar, both involving making "choices," resembling a parent-child relationship.

What exactly are the differences between them? Is it possible for backtracking algorithms and dynamic programming to be converted into each other?

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