AlgoPressAppearance
0416-分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
思路：回溯法，会超时
- 求出总和
- 回溯法求子集的和
- 判断，如果发现子集和 == 总和-子集的和，说明成立，回溯完成说明失败
参考代码
csharp
public class Solution {
private int totalSum;
private int sum1;
private bool canPartition = false;
private void dfs(int[] nums, int startIndex){
if(startIndex >= nums.Length){
return;
}
if(sum1 * 2 == totalSum){
canPartition = true;
return;
}
//选他
sum1+=nums[startIndex];
dfs(nums,startIndex+1);
sum1-=nums[startIndex];
//不选他
dfs(nums,startIndex+1);
}
public bool CanPartition(int[] nums) {
for(int i=0; i<nums.Length; i++){
totalSum+=nums[i];
}
dfs(nums,0);
return canPartition;
}
}
思路2：错误
将数组排列，双指针从前往后计算和值是否等于一半 算法错误：2,3,4,8,9,14 和的一半是 20， 2,4,14 不是连续的
csharp
public class Solution {
private int totalSum;
public bool CanPartition(int[] nums) {
Array.Sort(nums);
for(int i=0; i<nums.Length; i++){
totalSum+=nums[i];
}
if(totalSum % 2 == 1){
return false;
}
int halfSum = totalSum / 2;
int left = 0;
int right = 0;
int sum = 0;
while(left < right && right < nums.Length){
if(sum < halfSum){
sum+=nums[right];
right++;
}
else if(sum > halfSum){
sum-=nums[left];
left++;
}
else{
return true;
}
}
return false;
}
}
思路3：动态规划
设置状态： dp[i][j] 表示考虑下标[0,i] 这个区间的所有整数，在它们当中是否能够选出一些数，是的这些数之和恰好为整数j
参考代码
csharp
public class Solution {
public bool CanPartition(int[] nums){
if(nums.Length < 2){
return false;
}
//计算 sum
int sum=0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
if(sum % 2 == 1){ //如果是奇数无法完成分割
return false;
}
//设置动态规划数组
int target = sum / 2;
bool[,] dp = new bool[nums.Length,target+1];
// dp[i][j] 表示 [0,i] 这个区间的所有整数是否可以选出一些数，使得这些数之和恰好为整数j
//初始化
if(nums[0]<=target){
dp[0,nums[0]] = true;
}
for(int i=1; i<nums.Length; i++){
for(int j=0;j<=target;j++){
if(nums[i] == target){
dp[i,j]= true;
continue;
}
if(j-nums[i] >=0){
dp[i,j] = dp[i-1,j] || dp[i-1,j-nums[i]];
}
else{
dp[i,j]= dp[i-1,j];
}
}
}
return dp[nums.Length-1,target];
}
}
参考代码：使用滚动数组
csharp
public class Solution {
public bool CanPartition(int[] nums) {
//背包问题
//求nums数组中是否可以选择某些数达到 sum/2
// dp[i,j] 表示从 nums, 0 到 i 中选取一些数，和是否可以凑成 j
//求sum的一半
int sum = 0;
for(int i = 0; i < nums.Length; i++){
sum+=nums[i];
}
if(sum % 2 == 1){
return false;
}
int target = sum / 2;
//设置 dp
bool[] dp = new bool[target+1];
for(int i=0; i<nums.Length; i++){
for(int j=target;j>0;j--){
if(j >= nums[i]){
//三种情况
// 1. 正好等于，说明选他就行
// 2. 不选他，使用前面的结果
// 3. 选他，前面必须凑成他们的差
dp[j] = j == nums[i] || dp[j] || dp[j-nums[i]];
}
}
}
return dp[target];
}
}
复习：20220514
题目要求，分割成两个子集，和相等。
- 计算总和，如果是奇数直接返回，因为无法分为两部分
- 求出和 n/2 ，转换为题为从数中选择几个数，和为 n/2
- dp[i,j] 表示从0-i中选出几个数是否能凑成 j
csharp
public class Solution {
public bool CanPartition(int[] nums) {
//思路求和如果是奇数，则返回
//动态对话 dp[i,j] 表示从 0-i 中选出一些数，是否能凑成 j
// 状态转移 dp[i,j] = dp[i,j-nums[i]] || dp[i-1,j];
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
if(sum % 2 == 1){
return false;
}
int target = sum / 2;
//定义dp
bool[,] dp = new bool[nums.Length, target+1];
for(int i=0; i<nums.Length; i++){
dp[i,0] = true; //凑成0的可能性是 true，就是不放任何数字
}
if(nums[0] < target){
dp[0,nums[0]] = true;
}
//初始化
for(int i=1; i<nums.Length; i++){ //循环物品
for(int j=0; j<=target;j++){
if(j >= nums[i]){
dp[i,j] = dp[i-1,j] || dp[i-1,j-nums[i]];
}
else{
dp[i,j] = dp[i-1,j];
}
}
}
return dp[nums.Length-1,target];
}
}
- 使用滚动数组
- 定义 dp[i] 表示是否可以从数据找出数字凑成 i , 必须从后往前计算，防止重复运算
csharp
public class Solution {
public bool CanPartition(int[] nums) {
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
if( sum % 2 == 1){ //直接返回
return false;
}
sum = sum / 2; //转换为找出是否可以凑成数字 sum
bool[] dp = new bool[sum+1];
//初始化
//dp[0] = true; //0个数字可以凑成0
//状态转移
for(int j=0;j<nums.Length; j++){
for(int i=sum; i>=0; i--){ //问题：为什么要反向循环
if(i>=nums[j]){
dp[i] = dp[i] || i == nums[j] || dp[i-nums[j]];
}
}
//Console.WriteLine("dp[{0}]={1}",i,dp[i]);
}
return dp[sum];
}
}
复习:20220629
csharp
public class Solution {
public bool CanPartition(int[] nums) {
//01背包问题，从数字中选择一数字，看是否能凑成结果集
int sum = nums.Sum();
if(sum % 2 == 1){ //如果是奇数，则不可能凑成，返回 false
return false;
}
int target = sum / 2;
bool[] dp = new bool[target+1]; //定义dp数组， dp[j] 表示 i 之内的数是否能凑成j
dp[0] = true;
for(int i=0; i<nums.Length; i++){ //遍历物品
for(int j=target; j>=nums[i]; j--){ //遍历背包
dp[j] = dp[j] || dp[j-nums[i]]; //注意这里是或者关系，如果前面凑成功了，就是成功
}
}
return dp[target];
}
}