LeetCode LCR 101. 分割等和子集

Categories:

题目描述
思路分析
1. 解法一：0-1 背包（一维 DP）（推荐）
相似题目

题目描述

✅ LCR 101. 分割等和子集

思路分析

解法一：0-1 背包（一维 DP）（推荐）

核心思路：

问题转化：将数组分为两个等和子集，等价于能否从数组中选出若干数，使其和恰好等于 sum / 2，即 0-1 背包的可行性变体。

前置判断：若 sum 为奇数，不可能平分，直接返回 false；令 target = sum / 2。

状态定义：dp[j] 表示能否从数组中选出若干数使其和恰好为 j，初始 dp[0] = true，其余 false。

状态转移：对每个数 num，逆序遍历 j 从 target 到 num：dp[j] = dp[j] || dp[j - num]。

逆序遍历原因：若正序遍历，dp[j - num] 可能已被当前 num 更新过，导致 num 被重复使用（退化为完全背包）；逆序从大到小保证每个元素只使用一次。

复杂度分析：

时间复杂度：O(n × target)，其中 n 为数组长度，target = sum / 2

空间复杂度：O(target)，其中 target 为目标和

class Solution {
  public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    // 总和为奇数时，无法平分
    if (sum % 2 != 0) {
      return false;
    }
    int target = sum / 2;
    // dp[j] 表示能否凑出和为 j
    boolean[] dp = new boolean[target + 1];
    // 和为 0 始终可达
    dp[0] = true;
    for (int num : nums) {
      // 逆序遍历，保证每个元素只使用一次（0-1 背包）
      for (int j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
      }
    }
    return dp[target];
  }
}

func canPartition(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}

	// 总和为奇数时，无法平分
	if sum%2 != 0 {
		return false
	}

	target := sum / 2

	// dp[j] 表示能否凑出和为 j
	dp := make([]bool, target+1)
	// 和为 0 始终可达
	dp[0] = true

	for _, num := range nums {
		// 逆序遍历，保证每个元素只使用一次（0-1 背包）
		for j := target; j >= num; j-- {
			dp[j] = dp[j] || dp[j-num]
		}
	}

	return dp[target]
}

相似题目

题目	难度	考察点
494. 目标和	中等	0-1 背包计数（方案数）
698. 划分为 k 个相等的子集	中等	回溯 / 状压 DP
1049. 最后一块石头的重量 II	中等	0-1 背包（等价 416）
322. 零钱兑换	中等	完全背包求最少个数
474. 一和零	中等	二维 0-1 背包

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/81304960