经典动态规划：子集背包问题
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 416. Partition Equal Subset Sum | 🟠 |
Prerequisites
Before reading this article, you should learn:
In the previous article Classic Dynamic Programming: 0-1 Knapsack Problem, we detailed the general 0-1 knapsack problem. Today, let's see how the knapsack problem's approach can be applied to other algorithmic questions.
Moreover, readers often ask how to compress a two-dimensional dynamic programming problem into a one-dimensional one. This is called space compression, and it's quite simple. This article will also cover this technique.
Make sure you understand the patterns explained in the previous article Classic Dynamic Programming: 0-1 Knapsack Problem before reading this one, as this article follows the knapsack problem's solution template.
One, 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 this array can be partitioned into two subsets such that the sums of the elements in both subsets are 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) {};For example, if the input is nums = [1,5,11,5], the algorithm returns true because nums can be split into the two subsets [1,5,5] and [11].
If the input is nums = [1,3,2,5], the algorithm returns false because nums cannot be split into two subsets with equal sums no matter how you try.
At first glance, this problem seems to have nothing to do with the knapsack problem. Why is it considered a knapsack problem?
First, let's recall the general description of the knapsack problem:
You are given a knapsack with a maximum weight capacity W and N items, each with a weight and a value. The weight of the i-th item is wt[i] and its value is val[i]. The goal is to determine the maximum value you can store in the knapsack.
For our problem, we can start by calculating the sum of the array, which we'll call sum, and then transform the problem into a knapsack problem:
Given a knapsack with a maximum weight capacity of sum / 2 and N items, where each item's weight is nums[i], is there a way to pack the items such that the knapsack is exactly full?
You see, this fits the knapsack problem model, and it's even simpler than the classic knapsack problem we discussed before. Now, let's directly convert it into a knapsack problem and start applying the knapsack problem framework we discussed earlier.
II. Solution Analysis
The first step is to clarify two points: "state" and "choice".
This has been explained in detail in the previous article Classic Dynamic Programming: Knapsack Problem. The state refers to "the capacity of the knapsack" and "the available items," and the choice is whether to "put the item in the knapsack" or "not put it in."
The second step is to define the dp array.
Following the pattern of the knapsack problem, we can define it as follows:
dp[i][j] = x means that for the first i items (counting from 1), when the current capacity of the knapsack is j, if x is true, it indicates that the knapsack can be exactly filled. If x is false, it means the knapsack cannot be exactly filled.
For example, if dp[4][9] = true, it means that for a knapsack with a capacity of 9, if we only choose from the first 4 items, there is a way to fill the knapsack exactly.
Or, for this problem, it means that in the given set, if we only choose from the first 4 numbers, there exists a subset whose sum is exactly 9.
Based on this definition, the final answer we want is dp[N][sum/2]. The base cases are dp[..][0] = true and dp[0][..] = false, because when the knapsack has no space, it is considered full, and when there are no items to choose from, it is impossible to fill the knapsack.
Step 3: Think about the logic of state transition based on the "choice".
Recall the meaning of the dp array from earlier. Based on the "choice," we can derive the following state transitions for dp[i][j]:
If we do not include
nums[i]in the subset, or in other words, if you do not put thei-th item into the backpack, whether the backpack can be exactly filled depends on the previous statedp[i-1][j], inheriting the previous result.If we include
nums[i]in the subset, or in other words, if you put thei-th item into the backpack, whether the backpack can be exactly filled depends on the statedp[i-1][j-nums[i-1]].
相关信息
Since the i in the dp array definition starts counting from 1, while array indices start from 0, the weight of the i-th item should be nums[i-1]. Don't mix this up.
dp[i - 1][j-nums[i-1]] is also easy to understand: if you include the i-th item, you need to check if the remaining weight j - nums[i-1] can be exactly filled.
In other words, if the weight j - nums[i-1] can be exactly filled, then by adding the i-th item, the weight j can also be exactly filled; otherwise, the weight j definitely cannot be filled.
Final step: Translate the pseudocode into actual code and handle some edge cases.
Here is my Java code, which fully translates the previous thought process and handles some edge cases:
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
// when the sum is odd, it is impossible to partition into two subsets with equal sum
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[][] dp = new boolean[n + 1][sum + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// the backpack capacity is insufficient, cannot include the i-th item
dp[i][j] = dp[i - 1][j];
} else {
// either include or not include in the backpack
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
}class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// if the sum is odd, it is impossible to partition it into two subsets with equal sum
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// the backpack capacity is insufficient, cannot include the i-th item
dp[i][j] = dp[i - 1][j];
} else {
// either include or not include the item in the backpack
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
};class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = 0
for num in nums: s += num
# when the sum is odd, it is impossible to partition into two subsets with equal sum
if s % 2 != 0: return False
n = len(nums)
s = s // 2
dp = [[False for _ in range(s + 1)] for _ in range(n + 1)]
# base case
for i in range(0, n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, s + 1):
if j - nums[i - 1] < 0:
# the backpack capacity is insufficient, cannot include the i-th item
dp[i][j] = dp[i - 1][j]
else:
# include or not include in the backpack
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
return dp[n][s]func canPartition(nums []int) bool {
sum := 0
for _, num := range nums {
sum += num
}
// it is impossible to divide into two sets with equal sum when the total sum is odd
if sum%2 != 0 {
return false
}
n := len(nums)
sum = sum / 2
dp := make([][]bool, n+1)
for i := range dp {
dp[i] = make([]bool, sum+1)
}
// base case
for i := 0; i <= n; i++ {
dp[i][0] = true
}
for i := 1; i <= n; i++ {
for j := 1; j <= sum; j++ {
if j-nums[i-1] < 0 {
// the backpack capacity is insufficient, cannot include the i-th item
dp[i][j] = dp[i-1][j]
} else {
// either include or not include in the backpack
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
}
}
}
return dp[n][sum]
}var canPartition = function(nums) {
var sum = 0;
for (var i in nums) sum += nums[i];
// when the sum is odd, it is impossible to partition into two subsets with equal sum
if (sum % 2 != 0) return false;
var n = nums.length;
sum = sum / 2;
var dp = new Array(n + 1).fill().map(() => new Array(sum + 1).fill(false));
// base case
for (var i = 0; i <= n; i++)
dp[i][0] = true;
for (var i = 1; i <= n; i++) {
for (var j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// the backpack capacity is insufficient, cannot include the i-th item
dp[i][j] = dp[i - 1][j];
} else {
// include or not include in the backpack
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
};III. Further Optimization
Can we further optimize this code? Notice that dp[i][j] is always derived from the previous row dp[i-1][..], and the previous data is no longer used.
Therefore, we can refer to the previous article Dimensionality Reduction in Dynamic Programming and compress the two-dimensional dp array into one dimension to reduce space complexity:
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
// when the sum is odd, it is impossible to partition into two subsets with equal sum
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[] dp = new boolean[sum + 1];
// base case
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
}class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// when the sum is odd, it is impossible to divide into two subsets with equal sum
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
};class Solution:
def canPartition(self, nums: List[int]) -> bool:
sumn = 0
for num in nums:
sumn += num
# if the sum is odd, it is impossible to partition it into two subsets with equal sum
if sumn % 2 != 0:
return False
n = len(nums)
sumn = sumn // 2
dp = [False] * (sumn + 1)
# base case
dp[0] = True
for i in range(0, n):
for j in range(sumn, -1, -1):
if j - nums[i] >= 0:
dp[j] = dp[j] or dp[j - nums[i]]
return dp[sumn]func canPartition(nums []int) bool {
sum := 0
for _, num := range nums {
sum += num
}
// if the sum is odd, it is impossible to partition into two subsets with equal sum
if sum%2 != 0 {
return false
}
n := len(nums)
sum /= 2
dp := make([]bool, sum+1)
// base case
dp[0] = true
for i := 0; i < n; i++ {
for j := sum; j >= 0; j-- {
if j - nums[i] >= 0 {
dp[j] = dp[j] || dp[j-nums[i]]
}
}
}
return dp[sum]
}var canPartition = function(nums) {
let sum = nums.reduce((a, b) => a + b, 0);
// when the sum is odd, it is impossible to partition into two subsets with equal sum
if (sum % 2 !== 0) return false;
let n = nums.length;
sum = sum / 2;
let dp = new Array(sum + 1).fill(false);
// base case
dp[0] = true;
for (let i = 0; i < n; i++) {
for (let j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
};Actually, this code follows the same logic as the previous solution, operating only on a single line of the dp array. With each iteration of i, dp[j] essentially corresponds to dp[i-1][j], so a one-dimensional array is sufficient.
The only thing to note is that j should be iterated in reverse order, from back to front. This is because each item (or number) can only be used once, to prevent previous results from affecting others.
With this, the subset sum problem is completely solved, with a time complexity of O(n*sum) and a space complexity of O(sum).
