经典动态规划：子集背包问题

上篇文章 经典动态规划：0-1 背包问题 详解了通用的 0-1 背包问题，今天来看看背包问题的思想能够如何运用到其他算法题目。

读者在阅读本文之前务必读懂前文 经典动态规划：0-1 背包问题 中讲的套路，因为本文就是按照背包问题的解题模板来讲解的。

一、问题分析

看一下力扣第 416 题「分割等和子集」：

输入一个只包含正整数的非空数组 nums，请你写一个算法，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等。

算法的函数签名如下：

// 输入一个集合，返回是否能够分割成和相等的两个子集
boolean canPartition(int[] nums);

// 输入一个集合，返回是否能够分割成和相等的两个子集
bool canPartition(vector<int>& nums);

# 输入一个集合，返回是否能够分割成和相等的两个子集
def canPartition(nums: List[int]) -> bool:

// 输入一个集合，返回是否能够分割成和相等的两个子集
func canPartition(nums []int) bool {}

// 输入一个集合，返回是否能够分割成和相等的两个子集
var canPartition = function(nums) {};