Leetcode 416 Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

• Soruda pozitif sayılardan oluşan bir liste veriliyor ve bu listenin içinde toplamları birbirine eşit iki alt küme var mı diye soruyor.Var ise True yok ise False dönmemiz gerekiyor.
• nums = [1,5,11,5] burada [1,5,5] toplamı [11] listesine eşit True döneriz.
• Burada bir set liste oluştururuz ve nums listesindeki sayıları tek tek bu listedeki toplamlara ekleriz böylelikle nums listesi içerisindeki tüm toplama varyasyonları elimizde olur.Eğer nums içerisindeki sayıların toplamının yarıs bu listede varsa demek ki istenen koşul oluşmuştur.
• nums = [1,5,11,5] -> [5] için toplam listemiz dp = {0,5} listemize 0 koymamız gerekir ki farklı toplama varyasyonlarını kaçırmayalım.
• nums = [1,5,11,5] -> [11] için dp = {0,5,11,16} 11 bulduk aslında burada bitirebiliriz ama devam edelim.
• nums = [1,5,11,5] -> [5] için dp = {0,5,11,16,10,21} listeye 5 ve 16 koymadık çünkü set olarak oluşturmuştuk.
• Tüm nums listesini dolaştıktan sonra içinde nums toplamının yarısı var mı diye bakarız.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) %2 :
            return False
        
        dp = set()
        dp.add(0)
        target = sum(nums) // 2
        
        for i in range(len(nums) -1, -1, -1):
            nextDP = set()
            for t in dp:
                if(t + nums[i]) == target:
                    return True
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
        return True if target in dp else False