416. Partition Equal Subset Sum (Java, DP, Leetcode)

 

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        
        for (int i : nums) {
            sum += i;
        }
        
        if (sum % 2 != 0) 
            return false;
        
        sum /= 2;
        //decided whether it could be partitioned or not.
        
        //initialize the dp array size + 1 because there is an option sum nothing from the array and it will be always true.
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        
        //iterate the nums loop
        for (int num : nums) {
            //we will top down from the very largest sum.
            for (int j = sum; j >= 0; j--) {
                //if the value of present sum is greater than or equal to the present array
                if (j >= num) {
                    //dp[j - num] means if exclusion the num from the sum is true then inclusion the num to sum also true.
                    dp[j] |= dp[j - num];
                    //once dp[sum] is decided to be true, no need to proceed anymore.
                    if (dp[sum]) return true;
                }
            }
        }
        return false;
    }
}

 

해당 문제의 가장 핵심적인 부분은 다음의 double loop를 돌며 점화식을 iterating하는 부분이다.

코드를 말로 풀어 쓰자면 다음과 같다.

 

nums라는 배열을 처음부터 돌건데 num이 dp 배열에 저장되어 있니? (이때 num이 1이라면)
아니면 전체에서 num을 뺀 부분합이 저장되어 있니? (전체 11, 부분합 10)
아니면 전체에서 부분합을 1씩 빼면서라도 저장되어 있니? (전체 10, 부분합 9 , 전체 9, 부분합 8 ... 전체 1, 부분합 0)

num이 5라면 
전체 11, 부분합 6
전체 10, 부분합 5
...
전체 5, 부분합 0

 

        for (int num : nums) {
            for (int j = sum; j >= 0; j--) {
                if (j >= num) {
                    dp[j] |= dp[j - num];
                    if (dp[sum]) return true;
                }
            }
        }

 

DP의 핵심은 부분합을 뺀 나머지를 합으로 만들어낼 수 있다면 부분합을 더한 전체도 합으로 만들어낼 수 있다는 것이다.

 

dp[sum]을 만들어낼 수 있는 수많은 부분합을 또 수많은 부분합으로 나눠가며 부분합의 부분합들이 성립하는지 확인하는지 여부만 저장해두고

나중에 그 값을 가져다가 쓰기만 하면 되는 것이다.