# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
# Time: O(n * s) where s -> sum of nums
# Space: O(n * s)

def subset_partition(nums):
    n = len(nums)
    s = sum(nums)
    if s % 2:    return False
    target = s // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for i in range(n):
        dp2 = [True]
        for j in range(1, target + 1):
            if j < nums[i]:    dp2.append(dp[j])
            else:    dp2.append(dp[j] or dp[j - nums[i]])
        dp = dp2
    return dp[-1]

if __name__=='__main__':
    print(subset_partition([2, 3, 5, 6]))
# -



StarcoderdataJupyterScriptsDedupFiltered