416. Partition Equal Subset Sum (Leet Code)

아래의 Leetcode 문제를 풀다 잘 이해가 안가서 더 찾아보게 되었다. 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

// ex) nums = [1,5,11,5]
var canPartition = function(nums) {
	//Array의 총 합을 구함 totalSum = 22
    let totalSum = nums.reduce((acc, curr) => acc + curr);
    //Array를 같은 합을 가진 하위 Array 2개로 나누는 거다 보니, 짝수일 경우 return false 
    if (totalSum % 2) return false;

	//하위 Array 2개를 가지기 위해서는 Array의 합이 기존 nums Array의 1/2한 값을 가지게 될 경우임.
    const target = totalSum / 2;
    const memo = new Set([0]);

    for (let number of nums) {
        let possibleSums = Array.from(memo);
        for (let possibleSum of possibleSums) {
        //nums Array를 모두 돌면서 모든 값들의 합을 memo Set에 추가함.
        //ex){0,1,5,6,11,12,16,17}
            memo.add(possibleSum + number);
        }
    }
    //추가된 배열내 각 요소들의 합이 Target과 같다면, 가능하다는 결론이 나옴.
    //해당 케이스의 경우 11이 존재하기 때문에, true 반환
    //ex){0,1,5,6,11,12,16,17}
    return memo.has(target);
 }

 

brute force 방법으로 모든 값을 때려 넣어서 위와 같이 답을 구할 수는 있지만, 이중 포문으로 배열의 길이가 길어질 수록 시간 복잡도가 어마어마하게 증가하게 된다.

이 문제는 Dynamic Programming으로 해결을 할 수 있다고한다. 

Dynamic Programming을 사용하면, 한번 구한 값을 Memoization을 사용하여 한번 계산된 값을 다시 구할 필요가 없게 하여 시간 복잡도를 줄일 수 있다. (예를들어 피보나치 수열과 같이)

0/1 Knapsack Problem을 통해서 구할 수 있는거 같은데, 사실 아직 완벽하게 이해가 가진 않는다.
(빠르게 이해해서 적어보고 싶었지만, 잘 이해가 가지않아 좀 더 시간을 들여서 봐보려고 한다.)

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    let s = 0;
    for (let v of nums) {
        s += v;
    }
    if (s % 2 != 0) {
        return false;
    }
    const m = nums.length;
    const n = s >> 1;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= m; ++i) {
        for (let j = n; j >= nums[i - 1]; --j) {
            dp[j] = dp[j] || dp[j - nums[i - 1]];
        }
    }
    return dp[n];
};

아직 좀더 공부를 해봐야할것 같다. 

참조 
마나체스님의 네이버 블로그 https://blog.naver.com/manaches/223033005453
인도 유튜브 아저씨 https://www.youtube.com/watch?v=34l1kTIQCIA
안경잡이 개발자 (나동빈님의 블로그) https://blog.naver.com/ndb796/221233570962