上海市开办企业一窗网上服务,seo优化标题 关键词,自学网站建设和seo,小程序 wordpress来源#xff1a;LeetCode第416题
难度#xff1a;中等
描述#xff1a;给你一个只包含正整数的非空数组nums,请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等
分析#xff1a;相当于从nums数组中选取一些元素#xff0c;使得他们的和为…来源LeetCode第416题
难度中等
描述给你一个只包含正整数的非空数组nums,请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等
分析相当于从nums数组中选取一些元素使得他们的和为总和/2
递归求解
public Boolean getSum(int []nums)
{
int sum0;
for(int number:nums)
{
sumnumber;
}
if(sum%2!0)
{return false;
}
return GetSum(nums,sum/2,0)
}
public Boolean GetSum(int []nums,int sum,int index)
{
if(indexnums.length)
{
if(sum0)
{
return 1;
}else
{
return 0;
}
}return GetSum(nums,sum-nums[index],index1)||GetNum(nums,sum,index1);
}
可以看做是一个背包问题dp[i][j]表示前i个字符是否能组成和为j的部分dp[i][j]dp[i-1][j]dp[i-1][j-nums[i]];
public Boolean getSum2(int[]nums)
{
int sum0;
for(int number:nums)
{
sumnumber;
}
if(sum%2!0)
{
return false;
}
Boolean dp[][]new Boolean [nums.length][sum1];
if(nums[0]0)
{
dp[0][0]true;
}else{
dp[0][0]false;
}
for(int i1;inums.length;i)
{
if(nums[i]0)
{
dp[i][0]true;
}else
{
dp[i][0]dp[i-1][0];
}
}for(int i1;inums.length;i)
{
for(int j0;jsum1;j)
{
if(nums[i]j)
{
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][num1];
}
