本文主要是介绍代码随想录算法训练营第三十八天|416. 分割等和子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
416. 分割等和子集
public boolean canPartition(int[] A) {int N = A == null ? 0 : A.length;if (N <= 0) {return true;}// 数组求和int s = 0;for (int x : A) {s += x;}// 如果为奇数,肯定是没有办法切分if ((s & 0x01) == 1) {return false;}//分割为等和,那么相当于要取同值的一半final int V = s >> 1;// 这个dp表示着一开始可以访问的点集// 我们用true表示这个点存在于点集中// 分割为等和,那么相当于要取同值的一半// 这个dp表示着一开始可以访问的点集// 我们用true表示这个点存在于点集中// false表示这个点不存在点集中boolean[] dp = new boolean[V + 1];//首先初始集合肯定是s0={0}dp[0] = true;// 开始利用ai]来进行推导for (int x : A) {//注意这里更新的方向for (int node = V; node - x >= 0; node--) {final int newNode = node;final int oldExistsNode = node - x;if (dp[oldExistsNode]) {dp[newNode] = true;}}}return dp[V]; }
这篇关于代码随想录算法训练营第三十八天|416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!