# input: a[0..N) array of integers, N>=0, and S## output: is there a subarray of a[0..N) whose sum is S?## exponential (in N ans S) naive solutiondefss_naive(a,S):returnss_aux(a,len(a),S)defss_aux(a,n,s):ans=Noneifn==0:ans=(s==0)else:ifa[n-1]>s:ans=ss_aux(a,n-1,s)else:ans=max(ss_aux(a,n-1,s),ss_aux(a,n-1,s-a[n-1]))
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.