.leetcode(416. Partition Equal Subset Sum)

문제

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

문제 풀기 전

1. (잘못된 생각) 정렬한다음에 앞에서 출발해서 더하고, 뒤에서 부터 출발해서 더하면 되지 않을가.
2. (잘못된 생각) 역시 합문제는 더하고 봐야된다. [1,1,2,2]는 안되는구나
3. (잘못된 생각) 같은 숫자 쌍은 없애자. [1,5,5,11]
4. 39. Combination Sum 하고 비슷한 느낌을 받았다.

직접 푼 풀이

소요시간: 41분(17:17 ~ 17:58)

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

        Arrays.sort(nums);

        int half = sum/2;

        cache = new int[201][half+1];
        for (int i=0; i<201; i++) {
            Arrays.fill(cache[i], -1);
        }
        return solve(nums, 0, half);
    }

    private boolean solve(int[] nums, int index, int sum) {
        if (sum == 0) {
            return true;
        } else if (sum < 0) {
            return false;
        }

        if (cache[index][sum] != -1) {
            return cache[index][sum] == 1;
        } 

        for (int i=index; i<nums.length; i++) {
            if (sum >= nums[i]) {
                boolean result = solve(nums, i+1, sum - nums[i]);
                if (result) {
                    cache[index][sum] = 1;
                    return true;
                }
            }
        }

        cache[index][sum] = 0;
        return false;
    }
}

느낀점

1. 결국에는 원하는 부분합을 구하는 문제로 바뀌었다. 당연히 2개로 쪼갤 수 있으니 2의 배수의 수여야하고, 그러면 부분합으로 전체 총합의 1/2값을 구할 수 있어야한다. 구하는 순간, 정답으로 확인할 수 있는데 속도 측면이 효율적으로 개선하고자 memoization을 사용하였다.
2. 494. Target Sum에서 dp의 접근법을 배웠었는데 이렇게 한정적인 합에 접근할때는 아래와 같이 풀어 볼 수 있다.

솔루션 공부 후 추가로 푼 풀이

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

        int half = sum/2;
        boolean[][] dp = new boolean[nums.length+1][half+1];
        dp[0][0] = true;
        for(int i=1; i<=nums.length; i++) {
            int curr = nums[i-1];
            for(int j=0; j<half+1; j++) {
                if (j < curr) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j -curr];
                }
            }
        }
        return dp[nums.length][half];
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• dp로 풀어보기