Leetcode 416. Partition Equal Subset Sum

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

Partition Equal Subset Sum - LeetCode

 

---

이 문제는 처음에 만만하게 보고 간단한 코드를 짰다가 에러가 나서 애를 먹은 문제입니다 ㅜㅠ

 

여러 풀이를 보면서 어떤 식으로 해결 될 수 있는지 보겠습니다.

 

---

 

Brute-Force

class Solution:
    def canPartition(self, nums):
        def subsetSum(s, i=0):
            if s == 0: return True
            if i >= len(nums) or s < 0: return False
            return subsetSum(s-nums[i], i+1) or subsetSum(s, i+1)
        total_sum = sum(nums)
        return total_sum & 1 == 0 and subsetSum(total_sum // 2)

여기서 total_sum & 1 ==0 은 total_sum %2 ==0 을 의마합니다

 

Dynamic Programming - Memoization

위 풀이에 @cache를 통해 효율성을 높였습니다

class Solution:
    def canPartition(self, nums):
        @cache
        def subsetSum(s, i):
            if s == 0: return True
            if i >= len(nums) or s < 0: return False
            return subsetSum(s-nums[i], i+1) or subsetSum(s, i+1)
        total_sum = sum(nums)
        return total_sum & 1 == 0 and subsetSum(total_sum // 2, 0)

 

 

Dynamic Programming - Tabulation

class Solution:
    def canPartition(self, nums):
        total_sum = sum(nums)
        if total_sum & 1: return False
        half_sum = total_sum // 2
        dp = [True] + [False]*half_sum
        for num in nums:
            for j in range(half_sum, num-1, -1):
                dp[j] |= dp[j-num]
        return dp[half_sum]

 

 

DFS + Memoization

def canPartition(nums):
	s, n, memo = sum(nums), len(nums), {0: True}
        if s & 1: return False
        nums.sort(reverse=True)
        def dfs(i, x):
            if x not in memo:
                memo[x] = False
                if x > 0:
                    for j in range(i, n):
                        if dfs(j+1, x-nums[j]):
                            memo[x] = True
                            break
            return memo[x]
        return dfs(0, s >> 1)

위에 @cache를 쓴것과 달리 ㅡ 여기서는 memo형태로 memoization을 구현했습니다