[LeetCode] 416. Partition Equal Subset Sum

😎풀이

1. 총합 연산
2. 목표치는 총합의 절반이므로, 홀수가 될 수 없음
3. nums 순회
   3-1. 목표 값에서 현재 요소(nums[i])의 값을 뺀 값을 만들 수 있는 경우, 목표 값 또한 만들 수 있음
4. 최종 목표 값(총합의 절반)을 만들 수 있다면 true, 아니라면 false 반환

function canPartition(nums: number[]): boolean {
    const sum = nums.reduce((acc, cur) => acc + cur, 0)
    if((sum & 1) === 1) return false
    const target = sum / 2
    const dp = Array.from({ length: target + 1 }, () => false)
    dp[0] = true
    for(const num of nums) {
        for(let i = target; i >= num; i--) {
            if(!dp[i - num]) continue
            dp[i] = true
        }
        if(dp[target]) return true
    }
    return false
};