4/15

'''
nums = [1,5,11,5]

base case:
len=0->true
len=1->False


Recursive:
col->target=sum(num)//2 target->10 --> dp
rows->len(nums)

matrix

  0 1                           11
0   T F  F F F
1          t
2
3

  0 1
0 t F
1 F x
dp[target-nums[1]]

matrix[i][j] = True, what does this mean about the problem?

with numbers till index i of nums-> I can genertae j value

matrix[n][target] -> answer to your code.

let's say you know matrix[i][j] for all i,j <= m,n
matrix[i][j+1], matrix[i+1][j]

Given this, how can you solve matrix[i+1][j+1]


case1->subtract the target with my index at 1 and then  check for the remaining value within dp
dp[i][j]->dp[i][target-nums[i]]

case2->dp[i-1][target] I will not consider the number at index 1 and hence I am lookimng at previous calculated indexes.

dp[i][j] = dp[i-1][target-nums[i]] OR dp[i-1][target]




1. Establish base case
2. Establish recursive call.
3. write outhe basic example on paper with your method. Double check that it works.
4. Then write the code.
'''

def carPartition(nums):
    if sum(nums) % 2 == 1:
        return False

    # Initialize DP Array.
    # Recall dp[i][j] = True if with numbers till index i of nums-> I can genertae j value
    dp = []
    for _ in range(len(nums)):
        dp.append([False for _ in range(sum(nums) // 2 + 1)])

    # Base Case
    # len=0->true
    # This is the only base-case becuase dp[0][nums[0]] = True because 0 should include the first number. Everything else False because there's only one number.

    dp[0][0] = True
    if nums[0] <= sum(nums) // 2:
        dp[0][nums[0]] = True

    # Recursive step. Compute with DP.
    for i in range(1, len(nums)):
        for j in range(sum(nums) // 2 + 1) :
            print(i,j, nums[i])
            for row in dp:
                print(row)
            print("\n")
            if nums[i] <= j and dp[i-1][j-nums[i]]:
                dp[i][j] = True
            if i > 0 and dp[i-1][j]:
                dp[i][j] = True



    return dp[-1][-1]

print("Answer should be false, but is : ", carPartition([1,2,5])) # Should be false.

# carParition(


# def canPartition(nums):
#     sumation=sum(nums)
#     if sumation%2 !=0:
#         return False
#     target=sumation//2
#     dp=[[-1 for i in range(target+1)] for j in range(len(nums))]
#     def _can_partition(sum,indx):
#         if indx>=len(nums) :
#             return False
#         if dp[indx][sum]==-1:
#             inclu=_can_partition(sum-nums[indx],indx+1)
#             exclu=_can_partition(sum,indx+1)
#             dp[indx][sum]=inclu or exclu
#         return dp[indx][sum]
#     _can_partition(target,0)
#     print(dp)