[leetcode #416] Partition Equal Subset Sum

Problem

Given a non-empty array nums 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.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

・ 1 <= nums.length <= 200
・ 1 <= nums[i] <= 100

Idea

주어진 배열이 동일한 합을 가진 subarray 두 개로 나눠지는지 확인하는 문제다. 못 풀다가 Discussion의 풀이를 보고 이해를 했다.

우선 배열의 합을 구하고 2로 나눈 나머지가 0이 아니면 false를 리턴한다.

다음으로 dp를 만드는데, dp는 배열의 index를 기준으로 값이 만들어질 수 있는지 여부를 확인한다. 그래서 2-d array로 배열을 만들고 행은 배열의 크기, 열은 값으로 정한다. 해당 index까지 값을 기준으로 값을 만들 수 있는지 여부를 저장하는 boolean array가 바로 dp다.

배열을 탐색하면서 우선 행이나 열이 0이면 false로 설정을 한다. 이는 이전 dp를 탐색하여 값을 만들지 여부를 결정해야 되기 때문이기도 하고, 0을 만들 수 없기 때문이기도 하다.

만약 배열의 값이 j보다 크다면 이전 dp에서 j를 만들 수 있는지 여부를 그대로 설정한다. 단지 현재 index의 값을 사용하지 않으면 j값을 만들 수 있기 때문이다.

현재 배열의 값이 j와 같다면, 현재 배열의 값만 이용해 j를 만들 수 있다는 뜻이므로 그대로 true로 설정한다.

그 외의 경우는 이전 dp값이 true이거나 이전 dp값에서 j에서 현재 값을 뺀 값이 true로 설정되어 있으면 dp 값도 true로 설정된다. 이는 이전 배열에서 (j - 현재값)을 만들 수 있다면 현재값을 더하는 것으로 j를 만들 수 있기 때문이다.

모든 dp를 탐색한 뒤 마지막 index 값을 리턴하면 된다.

Solution

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;

        for (int i : nums)
            sum += i;

        if (sum % 2 != 0)
            return false;

        int half = sum / 2;
        boolean[][] dp = new boolean[n+1][half+1];

        for (int i=0; i <= n; i++) {
            for (int j=0; j <= half; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = false;
                else if (nums[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else if (nums[i-1] == j)
                    dp[i][j] = true;
                else
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
            }
        }

        return dp[n][half];
    }
}

Reference

https://leetcode.com/problems/partition-equal-subset-sum/