分割等和子集

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（面试手撕 LC Hot 100(ACM模式版)），可解锁完整内容。

购买题库开通会员

思路问题转化：给定一个数组，是否能从数组中选出一个子集，使得其和恰好为数组总和的一半。（这样没被选中的那一半一定也是数组总和的一半，两者的和相等）

1.问什么定义什么

$dp_{i,j}$ 代表 是否能从前 $i$ 个数中选出一个子集使得其和恰好为 $j$

$dp_{i,j} \in \{True , False\}$

题目描述

给定一个只包含正整数的非空数组 nums。

请判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

如果可以分割，输出 true；否则输出 false。

输入一行正整数，表示数组 nums 中的元素，整数之间用空格分隔。

如果可以将数组分割成两个元素和相等的子集，输出 $true$ ,否则输出 $false$

1 5 11 5

true

数组可以分割成 [1, 5, 5] 和 [11]。

两个子集的元素和均为 11，因此输出 true。

1 2 3 5

false

数组不能分割成两个元素和相等的子集，因此输出 false。

$1 <= nums.length <= 200$ $1 <= nums[i] <= 100$

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析