Solved using recursion but can be trivially be converted into DP


  • 0
    S
    def partition_sum(arr, n, k):
        if k == 0:
            return True
        if k < 0 or n == 0:
            return False
        
        return partition_sum(arr, n-1, k) or partition_sum(arr, n-1, k-n)
    
    def is_partition_sum(arr):
        s = sum(arr)
        if s % 2 != 0:
            return False
        
        return partition_sum(arr, len(arr) - 1, s/2)
    
    arr = [6,2,2]
    print(is_partition_sum(arr))
    

    The partition_sum recursive function can be trivially be converted into a DP solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.