class Solution {
public:
bool canPartition(vector<int>& nums) {
}
};
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100相似题目
原站题解
rust 解法, 执行用时: 5 ms, 内存消耗: 2.3 MB, 提交时间: 2025-04-07 09:31:11
impl Solution {
// dfs
pub fn can_partition1(nums: Vec<i32>) -> bool {
let s = nums.iter().sum::<i32>() as usize;
if s % 2 != 0 {
return false;
}
fn dfs(i: usize, j: usize, nums: &[i32], memo: &mut [Vec<i32>]) -> bool {
if i == nums.len() {
return j == 0;
}
if memo[i][j] != -1 { // 之前计算过
return memo[i][j] == 1;
}
let x = nums[i] as usize;
let res = j >= x && dfs(i + 1, j - x, nums, memo) || dfs(i + 1, j, nums, memo);
memo[i][j] = if res { 1 } else { 0 }; // 记忆化
res
}
let n = nums.len();
let mut memo = vec![vec![-1; s / 2 + 1]; n]; // -1 表示没有计算过
// 为方便起见，改成 i 从 0 开始
dfs(0, s / 2, &nums, &mut memo)
}
// 递推
pub fn can_partition2(nums: Vec<i32>) -> bool {
let s = nums.iter().sum::<i32>();
if s % 2 != 0 {
return false;
}
let s = s as usize / 2; // 注意这里把 s 减半了
let n = nums.len();
let mut f = vec![vec![false; s + 1]; n + 1];
f[0][0] = true;
for (i, &x) in nums.iter().enumerate() {
let x = x as usize;
for j in 0..=s {
f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
}
}
f[n][s]
}
// 空间优化
pub fn can_partition(nums: Vec<i32>) -> bool {
let s = nums.iter().sum::<i32>();
if s % 2 != 0 {
return false;
}
let s = s as usize / 2; // 注意这里把 s 减半了
let mut f = vec![false; s + 1];
f[0] = true;
let mut s2 = 0;
for x in nums {
let x = x as usize;
s2 = (s2 + x).min(s);
for j in (x..=s2).rev() {
f[j] = f[j] || f[j - x];
}
if f[s] {
return true;
}
}
false
}
}
javascript 解法, 执行用时: 3 ms, 内存消耗: 56.2 MB, 提交时间: 2025-04-07 09:29:57
/**
* @param {number[]} nums
* @return {boolean}
*/
// dfs
var canPartition1 = function(nums) {
const s = _.sum(nums);
if (s % 2) {
return false;
}
const n = nums.length;
const memo = Array.from({length: n}, () => Array(s / 2 + 1).fill(-1)); // -1 表示没有计算过
function dfs(i, j) {
if (i < 0) {
return j === 0;
}
if (memo[i][j] !== -1) { // 之前计算过
return memo[i][j] === 1;
}
const res = j >= nums[i] && dfs(i - 1, j - nums[i]) || dfs(i - 1, j);
memo[i][j] = res ? 1 : 0; // 记忆化
return res;
}
return dfs(n - 1, s / 2);
};
// 递推
var canPartition2 = function(nums) {
let s = _.sum(nums);
if (s % 2) {
return false;
}
s /= 2; // 注意这里把 s 减半了
const n = nums.length;
const f = Array.from({length: n + 1}, () => Array(s + 1).fill(false));
f[0][0] = true;
for (let i = 0; i < n; i++) {
const x = nums[i];
for (let j = 0; j <= s; j++) {
f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
}
}
return f[n][s];
};
// 空间优化
var canPartition3 = function(nums) {
let s = _.sum(nums);
if (s % 2) {
return false;
}
s /= 2; // 注意这里把 s 减半了
const f = Array(s + 1).fill(false);
f[0] = true;
let s2 = 0;
for (const x of nums) {
s2 = Math.min(s2 + x, s);
for (let j = s2; j >= x; j--) {
f[j] = f[j] || f[j - x];
}
if (f[s]) {
return true;
}
}
return false;
};
// bitset
var canPartition = function(nums) {
let s = _.sum(nums);
if (s % 2) {
return false;
}
s /= 2;
let f = 1n;
for (const x of nums) {
f |= f << BigInt(x);
}
return (f >> BigInt(s) & 1n) === 1n;
};
python3 解法, 执行用时: 0 ms, 内存消耗: 17.6 MB, 提交时间: 2025-04-07 09:28:00
class Solution:
# dfs
def canPartition1(self, nums: List[int]) -> bool:
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> bool:
if i < 0:
return j == 0
return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)
s = sum(nums)
return s % 2 == 0 and dfs(len(nums) - 1, s // 2)
# 递推
def canPartition2(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2:
return False
s //= 2 # 注意这里把 s 减半了
n = len(nums)
f = [[False] * (s + 1) for _ in range(n + 1)]
f[0][0] = True
for i, x in enumerate(nums):
for j in range(s + 1):
f[i + 1][j] = j >= x and f[i][j - x] or f[i][j]
return f[n][s]
# 空间优化
def canPartition3(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2:
return False
s //= 2 # 注意这里把 s 减半了
f = [True] + [False] * s
s2 = 0
for i, x in enumerate(nums):
s2 = min(s2 + x, s)
for j in range(s2, x - 1, -1):
f[j] = f[j] or f[j - x]
if f[s]:
return True
return False
# bitset
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2:
return False
s //= 2
f = 1
for x in nums:
f |= f << x
return (f >> s & 1) == 1
java 解法, 执行用时: 7 ms, 内存消耗: 43.4 MB, 提交时间: 2025-04-07 09:26:17
import java.math.BigInteger;
class Solution {
// dfs
public boolean canPartition1(int[] nums) {
int s = 0;
for (int num : nums) {
s += num;
}
if (s % 2 != 0) {
return false;
}
int n = nums.length;
int[][] memo = new int[n][s / 2 + 1];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
return dfs(n - 1, s / 2, nums, memo);
}
private boolean dfs(int i, int j, int[] nums, int[][] memo) {
if (i < 0) {
return j == 0;
}
if (memo[i][j] != -1) { // 之前计算过
return memo[i][j] == 1;
}
boolean res = j >= nums[i] && dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);
memo[i][j] = res ? 1 : 0; // 记忆化
return res;
}
// 递推
public boolean canPartition2(int[] nums) {
int s = 0;
for (int num : nums) {
s += num;
}
if (s % 2 != 0) {
return false;
}
s /= 2; // 注意这里把 s 减半了
int n = nums.length;
boolean[][] f = new boolean[n + 1][s + 1];
f[0][0] = true;
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int j = 0; j <= s; j++) {
f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
}
}
return f[n][s];
}
// 空间优化
public boolean canPartition3(int[] nums) {
int s = 0;
for (int x : nums) {
s += x;
}
if (s % 2 != 0) {
return false;
}
s /= 2; // 注意这里把 s 减半了
boolean[] f = new boolean[s + 1];
f[0] = true;
int s2 = 0;
for (int x : nums) {
s2 = Math.min(s2 + x, s);
for (int j = s2; j >= x; j--) {
f[j] = f[j] || f[j - x];
}
if (f[s]) {
return true;
}
}
return false;
}
// bitset
public boolean canPartition(int[] nums) {
int s = 0;
for (int x : nums) {
s += x;
}
if (s % 2 != 0) {
return false;
}
s /= 2; // 注意这里把 s 减半了
BigInteger f = BigInteger.ONE;
for (int x : nums) {
f = f.or(f.shiftLeft(x)); // f |= f << x;
}
return f.testBit(s); // 判断 f 中第 s 位是否为 1
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 5.2 MB, 提交时间: 2025-04-07 09:24:10
// dfs
func canPartition1(nums []int) bool {
s := 0
for _, x := range nums {
s += x
}
if s%2 != 0 {
return false
}
n := len(nums)
memo := make([][]int8, n)
for i := range memo {
memo[i] = make([]int8, s/2+1)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var dfs func(int, int) bool
dfs = func(i, j int) bool {
if i < 0 {
return j == 0
}
p := &memo[i][j]
if *p != -1 { // 之前计算过
return *p == 1
}
res := j >= nums[i] && dfs(i-1, j-nums[i]) || dfs(i-1, j)
if res {
*p = 1 // 记忆化
} else {
*p = 0
}
return res
}
return dfs(n-1, s/2)
}
// 递推
func canPartition2(nums []int) bool {
s := 0
for _, num := range nums {
s += num
}
if s%2 != 0 {
return false
}
s /= 2 // 注意这里把 s 减半了
n := len(nums)
f := make([][]bool, n+1)
for i := range f {
f[i] = make([]bool, s+1)
}
f[0][0] = true
for i, x := range nums {
for j := 0; j <= s; j++ {
f[i+1][j] = j >= x && f[i][j-x] || f[i][j]
}
}
return f[n][s]
}
// 空间优化
func canPartition3(nums []int) bool {
s := 0
for _, x := range nums {
s += x
}
if s%2 != 0 {
return false
}
s /= 2 // 注意这里把 s 减半了
f := make([]bool, s+1)
f[0] = true
s2 := 0
for _, x := range nums {
s2 = min(s2+x, s)
for j := s2; j >= x; j-- {
f[j] = f[j] || f[j-x]
}
if f[s] {
return true
}
}
return false
}
// bitset
func canPartition(nums []int) bool {
s := 0
for _, x := range nums {
s += x
}
if s%2 != 0 {
return false
}
s /= 2
f := big.NewInt(1)
p := new(big.Int)
for _, x := range nums {
f.Or(f, p.Lsh(f, uint(x)))
}
return f.Bit(s) == 1
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 14 MB, 提交时间: 2025-04-07 09:21:48
class Solution {
public:
// 定义 dfs(i,j) 表示能否从 nums[0] 到 nums[i] 中选出一个和恰好等于 j 的子序列
bool canPartition1(vector<int>& nums) {
int s = reduce(nums.begin(), nums.end());
if (s % 2) {
return false;
}
int n = nums.size();
vector memo(n, vector<int>(s / 2 + 1, -1)); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
if (i < 0) {
return j == 0;
}
int& res = memo[i][j]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
return res = j >= nums[i] && dfs(i - 1, j - nums[i]) || dfs(i - 1, j);
};
return dfs(n - 1, s / 2);
}
// 递推
bool canPartition2(vector<int>& nums) {
int s = reduce(nums.begin(), nums.end());
if (s % 2) {
return false;
}
s /= 2; // 注意这里把 s 减半了
int n = nums.size();
vector f(n + 1, vector<int>(s + 1));
f[0][0] = true;
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int j = 0; j <= s; j++) {
f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
}
}
return f[n][s];
}
// 空间优化
bool canPartition3(vector<int>& nums) {
int s = reduce(nums.begin(), nums.end());
if (s % 2) {
return false;
}
s /= 2; // 注意这里把 s 减半了
vector<int> f(s + 1);
f[0] = true;
int s2 = 0;
for (int x : nums) {
s2 = min(s2 + x, s);
for (int j = s2; j >= x; j--) {
f[j] |= f[j - x];
}
if (f[s]) {
return true;
}
}
return false;
}
// bitset做法
bool canPartition(vector<int>& nums) {
int s = reduce(nums.begin(), nums.end());
if (s % 2) {
return false;
}
s /= 2;
bitset<10001> f; // sum(nums[i]) / 2 <= 10000
f[0] = 1;
for (int x : nums) {
f |= f << x;
}
return f[s]; // 判断 f 中第 s 位是否为 1
}
};
python3 解法, 执行用时: 1076 ms, 内存消耗: 13.4 MB, 提交时间: 2020-11-17 15:08:24
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 恰好装满的0-1背包问题
s, n = sum(nums), len(nums)
if s % 2 == 1:
return False
cap = s // 2
dp = [False] * (cap + 1)
dp[0] = True
for i in range(1, n+1):
for j in range(cap, nums[i-1]-1, -1):
dp[j] = dp[j] or dp[j-nums[i-1]]
return dp[cap]