子集和就是01背包问题
正整数数组分成"等和"子集
选一些数，使它们和等于sum/2。01背包问题，和值相当于容量。
递推式先从二维数组写法入手，设dp[i][j]表示[0..i]的子集和等于j是否可行，dp[i][j] = dp[i-1][j]/*不取数i*/ || dp[i-1][j-nums[i]]/*取数i*/，只依赖dp[i-1][]，可用一维数组写法。处理每个物品，逆序遍历各容量，d[j]=dp[j]||dp[j-num]
vector<bool> dp(sum + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = sum; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[sum];
数组分成“等和”的K个子集
分成k个子集，就只能回溯法。背包问题只能选一个子集，也就是分成两个子集。
正整数数组各项加上正负号，使它们和为S的方式数
问题即：分成两个子集，使它们差为S。设加正号的成子集和为A，加负号的成子集和为B，A-B=S, A+B=sum，所以A=(sum+S)/2,B=(sum-S)/2，要满足sum>=S且sum-S是偶数。
问题转变成：选一些数，使它们和等于(sum-S)/2（比(sum+S)/2遍历范围更小）。01背包问题，返回方式数。
递推式先从二维数组写法入手，设dp[i][j]表示[0..i]的子集和等于j的方式数，dp[i][j] = dp[i-1][j]/*不取数i*/ + dp[i-1][j-nums[i]]/*取数i*/。处理每个物品，逆序遍历各容量，d[j]+=dp[j-num]。
主要思想与第k步走+k或-k这题类似
分成"和最接近"的两个子集
int lastStoneWeightII(vector<int>& stones) {
// 分成和最接近的两个子集，求 和<=sum/2的最大子集，01背包
// 设dp[i][v]表示前i个数的子集和等于v是否可行。
// dp[i][v] = dp[i-1][v]/*不取nums[i]*/ || dp[i-1][v-num]/*取nums[i]*/。
// 递推式i这维依赖于i-1项，可省掉i这一维。dp[v] = dp[v] || dp[v-num]。v逆序遍历。
int sum = 0;
for (int w : stones)
sum += w;
vector<bool> dp(sum / 2, false);
dp[0] = true;
for (int w : stones) {
for (int v = sum / 2; v >= w; v--) {
dp[v] = dp[v] || dp[v-w];
}
}
for (int v = sum / 2; v >= 0; v--) {
if (dp[v]) return sum - v - v;
}
return -1; // invalid
}
分成“和最接近”的两个等长子集
从2n个数中选n个数，使它们的和最接近sum/2，不妨取<=sum/2的最大数。
设dp[i][k][v]表示从前i个数中取k个数、子集和等于v是否可行。考虑第i个数，dp[i][k][v]=dp[i-1][k][v]/*不取第i个数*/||dp[i-1][k-1][v-num]/*取第i个数*/。递推式i这维依赖于i-1项，可省掉i这一维。二维费用01背包问题，逆序遍历k和v：dp[k][v]=dp[k][v]||dp[k-1][v-num]
dp[0][0] = true;
for (int num : nums) {
// 01背包，逆序遍历k和v
for (int k = n; k >= 1; k--) {
for (int v = sum/2; v >= num; v--) {
dp[k][v] = dp[k][v] || dp[k-1][v-num];
}
}
}
最终取dp[n][sum/2..0]中第一个为true的。
类似ksum问题，二维费用背包问题
能被3整除的最大子集和
int maxSumDivThree(vector<int>& nums) {
// 设dp[i][j]表示nums[0..i]的被3除余j的最大子集和
// dp[i][j]=max(dp[i-1][j], dp[i-1][(j-nums[i])%3]+nums[i])
// 第i项只依赖于第i-1项，可省掉i这维，i仍从左往右遍历
// dp[j]=max(dp[j], dp[(j-num)%3]+num)=max(dp[j], dp[(j+2*num)%3]+num)
vector<int> dp({0, INT_MIN, INT_MIN});
for (int num : nums) {
vector<int> ndp(3);
for (int j = 0; j < 3; j++) {
ndp[j] = max(dp[j], dp[(j+2*num)%3] + num);
}
swap(dp, ndp);
}
return dp[0];
}
子集排列数
int combinationSum4(vector<int>& nums, int target) {
// 和为i的子集排列数 dp[i]=sum(dp[i-num])
// 子集排列数的写法刚好 将背包问题的外层物品循环改为内层
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int num : nums) {
if (i - num >= 0) dp[i] += dp[i-num];
}
}
return dp[target];
}