分割等和子集

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];

    }

}

参考
动态规划｜分割等和子集 - 知乎 (zhihu.com)