Classic DP: Subset Knapsack Problem

The previous article Classic Dynamic Programming: 0-1 Knapsack Problem detailed the general 0-1 knapsack problem. Today, let's see how the concept of the knapsack problem can be applied to other algorithmic problems.

Readers must understand the routine explained in the previous article Classic Dynamic Programming: 0-1 Knapsack Problem before reading this article, as this article explains according to the knapsack problem's solving template.

1. Problem Analysis

Take a 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 such that the sum of elements in both subsets is equal.

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) {};