Leetcode - 数组等和分割

问题

给定一个只包含正整数的非空数组。求是否可以将这个数组分割成两个子集，使得两个子集的元素和相等，数组由 nums 给出，返回bool。

思路

1. 动态规划：数组等和分割，可以拆分成能否从数组中找出和为一半的元素，显然该问题与背包问题极其相似。设dp[i][j]为是否能从数组 0 ~ i 号元素中选出和为j。分析不难发现当前数字可以选中或不选，若选中，则结果取决于dp[i-1][j-nums[i]]，若不选，则取决于dp[i-1][j]。得出状态方程dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]]
2. 深度优先：每个元素要么选中要么丢弃，展开得到一个二叉树，父节点取决于两个叶子节点的结果。

代码(C++)

DP

int sum=0;
const int N=nums.size();
for(int i=0;i<N;i++)
	sum+=nums[i];
if(sum & 1)
	return false;
const int S=sum/2;
bool dp[N][S+1];
//初始化
for(int i=0;i<N;i++)
	for(int j=0;j<=S;j++)
		dp[i][j]=false;

//第一个数(0 ~ 0)
for(int j=0;j<=S;j++)
	dp[0][j]=(j==nums[0]) ? true:false;

for(int i=0;i<N;i++)
	for(int j=0;j<=S;j++)
	{
		if(j<nums[i]
			dp[i][j]=dp[i-1][j];	//数字超过总和，只能舍弃
		else
			dp[i][j]=dp[i-1][j-nums[i]] || dp[i-1][j];
	}
return dp[N-1][S];

优化：稍作分析可以看出dp[i][j]只取决于dp[i-1][j]和dp[i-1][j-nums[i]]，两者相差一行，后一步dp可以直接覆盖前一步，将二维数组压缩到一维，空间复杂度降为O(S)。进一步分析可以得知，对于本题不要求给出所有可行方案的前提下，如果在前面的规划过程中得到了dp[S]为true的结果，可以直接返回。

优化DP

int sum=0;
const int N=nums.size();
for(int i=0;i<N;i++)
	sum+=nums[i];
if(sum & 1)
	return false;
const int S=sum/2;
bool dp[S+1];
//第一个元数(0 ~ 0)
for(int j=0;j<=S;j++)
	dp[j]=(j==nums[0]) ? true:false;
//第一个元素等于S，满足等和分割，直接返回
if(dp[s])
	return true;
for(int i=0;i<N;i++)
	for(int j=S;j>=nums[i];j--)		//优先规划和为S的情况。j<nums[i]时dp值等于前一步，直接跳过
	{	
		dp[j]=dp[j-nums[i]] || d[j];
		if(j==S && dp[j])
			return true;		//已有可行方案，直接返回
	}
return dp[S];

DFS

bool dfs(int i,int sum)
{
	if(sum==0)
		return true;
	if(i<0 || sum<0)		//边界条件
		return false;
	return dfs(i-1,sum) || dfs(i-1,sum-nums[i]);	//左右分支
}

int main()
{
	int sum=0;
	const int N=nums.size();
	for(int i=0;i<N;i++)
		sum+=nums[i];
	if(sum & 1)
		return false;
	const int S=sum/2;
	return dfs(N-1,S);
}

优化：如果用两个变量分别记录已选和丢弃元素的和，则可以实现左右剪枝。

优化DFS - 剪枝

bool dfs(int i,int sumL,int sumR)	//左分支选中，右分支丢弃
{
	if(sumL>S || sumR>S || i<0)		//丢弃或已选元素之和超过目标，直接剪枝
		return false;
	if(sumL==S || sumR==S)
		return true;
	return dfs(i-1,sumL+nums[i],sumR) || dfs(i-1,sumL,sumR+nums[i]);
}

int S;
int main()
{
	int sum=0;
	const int N=nums.size();
	for(int i=0;i<N;i++)
		sum+=nums[i];
	if(sum & 1)
		return false;
	S=sum/2;
	sort(nums.begin(),nums.end());		//预排序
	if(nums.back()>S)		//最大元素超过目标值
		return false;
	return dfs(N-1,0,0);
}