分割等和子集
2022-03-31 本文已影响0人
xiaohei_e853
image.png
image.png
image.png
image.png
image.png
image.png
第一版代码：
image.png
image.png
只用一维数组解决
image.png
public class CanPartion {
public static void main(String[] args) {
int[] nums = {1,5,11,5};
canPartion(nums);
}
public static boolean canPartion(int[] nums){
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum +=nums[i];
}
if(sum%2==1){
return false;
}
int target = sum/2;
boolean[] dp = new boolean[target+1];
dp[0] = true;
dp[nums[0]] = true;
for (int i = 0; i <nums.length ; i++) {
for (int j = target; j >0&&j>=nums[i] ; j--) {
int tmp = j-nums[i];
dp[j] = dp[j]||dp[j-nums[i]];
}
}
return dp[target];
}
}
