416. Partition Equal Subset Sum

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

Python

DFS (Failed Try)

Fail try, did not really get the idea... (2021/12/12)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if not nums:
            return False

        total = sum(nums)
        if total % 2:
            return False

        target = total / 2
        sorted_nums = sorted(nums, reverse=True)

        return self._dfs(sorted_nums, 0, target)

    def _dfs(self, nums, index, target):
        if target < nums[index]:
            return False

        target -= nums[index]
        if target == 0 or self._dfs(nums, index+1, target):
            return True
        target += nums[index]

Top Down DP

from functools import cache


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        nums.sort()

        @cache
        def dp(i: int, sum1: int, sum2: int):
            if i == len(nums):
                if sum1 == sum2:
                    return True
                return False

            num = nums[i]

            return dp(i+1, sum1, sum2+num) or dp(i+1, sum1+num, sum2)

        return dp(0, 0, 0)

JS

// top-down
var canPartition = function(nums) {
   const sum = nums.reduce((acc, cur) => acc + cur, 0);
   const subSum = Math.ceil(sum / 2);
    if (subSum * 2 !== sum) return false;
    
   const memo = {};
   const dfs = (i, curSum) => {
       const key = `${i}${curSum}`;
       // console.log(i, curSum)
       if (curSum === 0) return true;
       if (i === nums.length || curSum < 0) return false;
       if (memo.hasOwnProperty(key)) return memo[key];
       
       memo[key] = dfs(i + 1, curSum - nums[i]) || dfs(i + 1, curSum);
       return memo[key]
   }
   
   return dfs(0, subSum);
};

// bottom-up
var canPartition = function(nums) {
    const sum = nums.reduce((acc, cur) => acc + cur);
    if (sum % 2 !== 0) return false;
    
    const total = sum / 2;
    const dp = [...new Array(nums.length + 1)].map(() => [...new Array(total + 1)].fill(false));
    
    for (let i = 1; i <= nums.length; i++) {
        for (let j = 0; j <= total; j++) {
            if (j === 0) dp[i][j] = true;
            else {
                if (j - nums[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }        
    }
  
    return dp[nums.length][total];
};