Partition Equal Subset Sum

Question

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.

Solution

知道是用 DP 解，但想不出來，所以第一遍直接看解答。 這題講白了其實跟 house robber 核心概念很像，就是取或不取。我們知道要分成兩個 subset，每一個 subset 加總起來的值會是 sum/2。因此，在遍歷 array 的過程中，會面臨到該取這個值或不該取這個值。

state: dp[i][j] 代表前 i 個數能否加總成 j(sum/2) function: 如果決定不取，那麼 dp[i][j] = dp[i - 1][j]；如果決定要取，那 dp[i][j] = dp[i - 1][j - nums[i - 1]]。不取的情況比較好想，取的情況可以想成，如果我取了當前這個值，那就代表我前 i - 1 個的加總要等於 j - nums[i - 1] （用 nums[i - 1] 是因為 state 定義前 i 個，試想前三個其實是代表 index 只到 2）

initialize: dp[nums.length + 1][sum + 1]; dp[0][0] = true, dp[i][0] = true, dp[0][j] = false; answer: 求 dp[nums.length][sum]

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }

        sum /= 2;

        boolean[][] dp = new boolean[nums.length + 1][sum + 1];
        dp[0][0] = true;

        for (int i = 1; i <= nums.length; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= sum; i++) {
            dp[0][i] = false;
        }

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][sum];
    }