題目

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:

• Each of the array element will not exceed 100.
• 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.

解法思路（一）

狀態(tài)的定義

• F(n, C) 考慮用 n 個(gè)物品填滿容量為 C 的背包；

狀態(tài)的轉(zhuǎn)移過(guò)程

• F(i, C) = F(i-1, C) || F(i-1, C-w(i))；

解法實(shí)現(xiàn)（一）記憶化遞歸

關(guān)鍵字

動(dòng)態(tài)規(guī)劃 狀態(tài) 狀態(tài)轉(zhuǎn)移 記憶化遞歸

實(shí)現(xiàn)細(xì)節(jié)

• 注意狀態(tài)轉(zhuǎn)移方程的具體代碼和記憶數(shù)組 memo；

package leetcode._416;

import java.util.Arrays;

public class Solution416_2 {

    // memo[i][c] 表示使用索引為[0...i]的這些元素,是否可以完全填充一個(gè)容量為c的背包
    // -1 表示為未計(jì)算; 0 表示不可以填充; 1 表示可以填充
    private int[][] memo;

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] <= 0)
                throw new IllegalArgumentException("numbers in nums must be greater than zero.");
            sum += nums[i];
        }

        if(sum % 2 == 1)
            return false;

        memo = new int[nums.length][sum / 2 + 1];
        for(int i = 0 ; i < nums.length ; i ++)
            Arrays.fill(memo[i], -1);

        return tryPartition(nums, nums.length - 1, sum / 2);
    }

    // 使用nums[0...index], 是否可以完全填充一個(gè)容量為sum的背包
    private boolean tryPartition(int[] nums, int index, int sum){

        if(sum == 0)
            return true;

        if(sum < 0 || index < 0)
            return false;

        if(memo[index][sum] != -1)
            return memo[index][sum] == 1;

        memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
                tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;

        return memo[index][sum] == 1;
    }

    private static void printBool(boolean res){
        System.out.println(res ? "True" : "False");
    }

    public static void main(String[] args) {

        int[] nums1 = {1, 5, 11, 5};
        printBool((new Solution416_2()).canPartition(nums1));

        int[] nums2 = {1, 2, 3, 5};
        printBool((new Solution416_2()).canPartition(nums2));
    }

}

解法實(shí)現(xiàn)（一）動(dòng)態(tài)規(guī)劃

關(guān)鍵字

動(dòng)態(tài)規(guī)劃 狀態(tài) 狀態(tài)轉(zhuǎn)移 記憶化遞歸

實(shí)現(xiàn)細(xì)節(jié)

• 優(yōu)化過(guò)的，空間復(fù)雜度為 C 的動(dòng)態(tài)規(guī)劃的寫法；

package leetcode._416;

public class Solution416_3 {

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] <= 0)
                throw new IllegalArgumentException("numbers in nums must be greater than zero.");
            sum += nums[i];
        }

        if(sum % 2 == 1)
            return false;

        int n = nums.length;
        int C = sum / 2;

        boolean[] memo = new boolean[C + 1];
        for(int i = 0 ; i <= C ; i ++)
            memo[i] = (i == nums[0]);

        for(int i = 1 ; i < n ; i ++)
            for(int j = C; j >= nums[i] ; j --)
                memo[j] = memo[j] || memo[j - nums[i]];

        return memo[C];
    }

}

返回 LeetCode [Java] 目錄