leetcode416. Partition Equal Subset Sum

太过爱你忘了你带给我的痛 2022-03-08 13:26 178阅读 0赞

## 题目要求 ##

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
    
    Note:
    1.Each of the array element will not exceed 100.
    2.The array size will not exceed 200.
    Example 1:
    
    Input: [1, 5, 11, 5]
    
    Output: true
    
    Explanation: The array can be partitioned as [1, 5, 5] and [11].
    Example 2:
    
    Input: [1, 2, 3, 5]
    
    Output: false
    
    Explanation: The array cannot be partitioned into equal sum subsets.

假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。

## 思路和代码 ##

这和0-1背包问题是完全一样的，01背包问题是指假设有n个物品，每个物品中为weight\[i\]，假设背包的承重为k，问如何选择物品使得背包中的承重最大。而这里的问题等价于，有n个物品，每个物品承重为input\[i\]，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。

假设我们已经知道前i个物品是否能够构成重量k，我们令该值为dpi，那么第i+1个物品是否能够构成重量取决于dpi和dpi\], 即i+1个物品能够构成重量k有两种情况，第一种选择了i+1个物品，则要寻找前i个物品是否构成k-input\[i+1\]的重量，第二种就是没有选择第i+1个物品，则直接判断前i个物品是否已经构成了k的重量。

代码如下：

public boolean canParition(int[] nums) {
            int sum = 0;
            for(int n : nums) {
                sum += n;
            }
            if(sum % 2 != 0) return false;
            int half = sum / 2;
            boolean[][] sums = new boolean[nums.length+1][half+1];
            for(int i = 0 ; i<=nums.length ; i++) {
                for(int j = 0 ; j<=half ; j++) {
                    if(i==0 && j==0){
                        sums[i][j] = true;
                    }else if(i==0) {
                        sums[i][j] = false;
                    }else if(j==0){
                        sums[i][j] = true;
                    }else {
                        sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false);
                    }
                }
            }
            return sums[nums.length][half];
        }