Classic DP: Subset Knapsack Problem

In the previous article Classic Dynamic Programming: The 0-1 Knapsack Problem, we detailed the general 0-1 knapsack problem. Today, let's see how the ideas from the knapsack problem can be applied to other algorithm problems.

Readers must understand the routines explained in the previous article Classic Dynamic Programming: The 0-1 Knapsack Problem before reading this article, as this article follows the solution template of the knapsack problem.

1. Problem Analysis

Let's look at LeetCode Problem 416 "Partition Equal Subset Sum":

Given a non-empty array nums containing only positive integers, write an algorithm to determine if the array can be partitioned into two subsets with equal sum.

The function signature of the algorithm is as follows:

// input a set, return whether it can be partitioned into two subsets with equal sum
boolean canPartition(int[] nums);

// input a set and return whether it can be partitioned into two subsets with equal sum
bool canPartition(vector<int>& nums);

# input a set, return whether it can be partitioned into two subsets with equal sum
def canPartition(nums: List[int]) -> bool:

// input a set and return whether it can be partitioned into two subsets with equal sum
func canPartition(nums []int) bool {}

// input a set and return whether it can be partitioned into two subsets with equal sum
var canPartition = function(nums) {};