Iam_Sandeep

subset sum dynamic programming

Sep 23rd, 2021
859
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     def isSubsetSum (self, n, arr, sum):
  2.         # code here
  3.         sos=[[False]*(sum+1) for i in range(n+1)]
  4.         for i in range(sum+1):
  5.             sos[0][i]=False
  6.         for i in range(n+1):
  7.             sos[i][0]=True
  8.         for i in range(1,n+1):
  9.             for j in range(1,sum+1):
  10.                 if arr[i-1]>j:
  11.                     sos[i][j]=sos[i-1][j]
  12.                 else:
  13.                     sos[i][j]=sos[i-1][j] or sos[i-1][j-arr[i-1]]
  14.         return sos[-1][-1]
RAW Paste Data