LeetCode Solutions
416. Partition Equal Subset Sum
class Solution {
public:
bool canPartition(vector<int>& nums) {
const int sum = accumulate(begin(nums), end(nums), 0);
if (sum & 1)
return false;
return knapsack(nums, sum / 2);
}
private:
bool knapsack(const vector<int>& nums, int subsetSum) {
const int n = nums.size();
// dp[i][j] := true if j can be formed by nums[0..i)
vector<vector<bool>> dp(n + 1, vector<bool>(subsetSum + 1));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
const int num = nums[i - 1];
for (int j = 0; j <= subsetSum; ++j)
if (j < num)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
}
return dp[n][subsetSum];
}
};
class Solution {
public boolean canPartition(int[] nums) {
final int sum = Arrays.stream(nums).sum();
if (sum % 2 == 1)
return false;
return knapsack(nums, sum / 2);
}
private boolean knapsack(int[] nums, int subsetSum) {
final int n = nums.length;
// dp[i][j] := true if j can be formed by nums[0..i)
boolean[][] dp = new boolean[n + 1][subsetSum + 1];
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
final int num = nums[i - 1];
for (int j = 0; j <= subsetSum; ++j)
if (j < num)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
}
return dp[n][subsetSum];
}
}
class Solution:
def canPartition(self, nums: List[int]) -> bool:
summ = sum(nums)
if summ & 1:
return False
return self.knapsack_(nums, summ // 2)
def knapsack_(self, nums: List[int], subsetSum: int) -> bool:
n = len(nums)
# dp[i][j] := True if j can be formed by nums[0..i)
dp = [[False] * (subsetSum + 1) for _ in range(n + 1)]
dp[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for j in range(subsetSum + 1):
if j < num:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - num]
return dp[n][subsetSum]