[LC 416]. Partition Equal Subset Sum

背包问题,学习ing。一个array,问是否能分成和相等的两个部分,例如[1,5,7,11]可分为[1,11]和[5,7]所以是true,[1,2,5]是false。可以变换成:是否在array能找到几个数,他们的和为总和的一半。可以用2D数组做,略过。看看用1D数组做的:

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        sum = sum / 2; 
        ///////////////////
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = sum; i >= 0; i--) {
                if (i >= num) {
                    dp[i] = dp[i] || dp[i-num];
                }
            }
        }
        return dp[sum];
    }

分割线以上都没什么好说的。以下注意一个地方:i 从 sum 减少一直到0,而非从0增加到sum。反过来就错了。从意义上理解一下为什么。每次来一个新的num,要看选择或不选择这个num,是否可以使和为sum,如果i从下到大增加,可能会让dp中所有的元素都为true。看一个例子:
array: [1,2,5], sum = 8, sum = sum/2 = 4, dp has length sum+1 = 5.
i–的时候,dp的变化:
0 1 2 3 4
num = 1, dp = [T, T, F, F, F] (given number 1, we can get sum = 1)
num = 2, dp = [T, T, T, T, F] (given 2, get 2 by not taking 1, 3 by taking 1)
num = 5, dp = [T, T, T, T, F] (when i = 4, i < num, so nothing changes)

i++的时候,dp的变化
0 1 2 3 4
num = 1, dp = [T, T, T, T, T] (means when given num = 1, we can construct sum = 1, and 2 by taking one more 1, and 3 by taking one more 1, and 4 by taking one more 1. The procedure is impossible. We can take 1 once.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s