东莞手机网站价格表,适合个人开发的小程序创意,网站备案和icp备案,微信网站响应式网站问题背景
给你一个 只包含正整数 的 非空 数组 n u m s nums nums。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
数据约束 1 ≤ n u m s . l e n g t h ≤ 200 1 \le nums.length \le 200 1≤nums.length≤200 1 ≤ n u m s [ i ] ≤ …问题背景
给你一个 只包含正整数 的 非空 数组 n u m s nums nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
数据约束 1 ≤ n u m s . l e n g t h ≤ 200 1 \le nums.length \le 200 1≤nums.length≤200 1 ≤ n u m s [ i ] ≤ 100 1 \le nums[i] \le 100 1≤nums[i]≤100
解题过程
要求分成两个子集且和相等其实就是找到一个总和为 s u m / 2 sum / 2 sum/2 的子集其中 s u m sum sum 表示整个集合的和。需要注意的是 s u m sum sum 必须是偶数。 此外和为零是一种可能的状态所以记忆化数组中的元素要初始化为 − 1 -1 −1。 递归入口 是 d f s ( n − 1 , s u m / 2 ) dfs(n - 1, sum / 2) dfs(n−1,sum/2)表示在 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 的范围上找到一个和为 s u m / 2 sum / 2 sum/2 的子集。 递归边界 是 d f s ( − 1 , 0 ) t r u e dfs(-1, 0) true dfs(−1,0)true表示枚举完了整个集合中的所有元素最终能够使得剩余目标和减少到零。
翻译成递推时要注意数组下标不能为 − 1 -1 −1所以要进行转移将结果映射到 [ 1 , n ] [1, n] [1,n] 这个范围上。
具体实现
递归
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if ((sum 1) 1) {return false;}int n nums.length;int[][] memo new int[n][(sum 1) 1];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(n - 1, sum 1, nums, memo);}private boolean dfs(int i, int j, int[] nums, int[][] memo) {if (i 0) {return j 0;}if (memo[i][j] ! -1) {return memo[i][j] 1;}boolean res j nums[i] dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);memo[i][j] res ? 1 : 0;return res;}
}递推
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if ((sum 1) 1) {return false;}sum / 2;int n nums.length;boolean[][] dp new boolean[n 1][sum 1];dp[0][0] true;for (int i 0; i n; i) {int cur nums[i];for (int j 0; j sum; j) {dp[i 1][j] j cur dp[i][j - cur] || dp[i][j];}}return dp[n][sum];}
}空间优化
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if ((sum 1) 1) {return false;}sum / 2;int n nums.length;boolean[] dp new boolean[sum 1];dp[0] true;// minSum 表示前 i 个数和的上界不可能超过所有这些数的总和int minSum 0;for (int num : nums) {// 用这个值来初始化内层循环可以避免许多不必要的判断想不清楚的话直接用 sum 也可以minSum Math.min(minSum num, sum);for (int j minSum; j num; j--) {dp[j] dp[j] || dp[j - num];}if (dp[sum]) {return true;}}return false;}
}
