sum_of_subset.py

defis_sum_subset(arr: list[int], required_sum: int) ->bool:
"""
 >>> is_sum_subset([2, 4, 6, 8], 5)
 False
 >>> is_sum_subset([2, 4, 6, 8], 14)
 True
 """
# a subset value says 1 if that subset sum can be formed else 0
# initially no subsets can be formed hence False/0
arr_len=len(arr)
subset= [[False] * (required_sum+1) for_inrange(arr_len+1)]

# for each arr value, a sum of zero(0) can be formed by not taking any element
# hence True/1
foriinrange(arr_len+1):
subset[i][0] =True

# sum is not zero and set is empty then false
foriinrange(1, required_sum+1):
subset[0][i] =False

foriinrange(1, arr_len+1):
forjinrange(1, required_sum+1):
ifarr[i-1] >j:
subset[i][j] =subset[i-1][j]
ifarr[i-1] <=j:
subset[i][j] =subset[i-1][j] orsubset[i-1][j-arr[i-1]]

returnsubset[arr_len][required_sum]


if__name__=="__main__":
importdoctest

doctest.testmod()