# input: a[0..N) array of integers, N>=0, and S
#
# output: is there a subarray of a[0..N) whose sum is S?
#
# O(NS) time and space solution

def ss_tab(a,S):
  N = len(a)
  tab = [ [ None for s in range(S+1) ] for n in range(N+1) ]
  for s in range(S+1): tab[0][s] = (s==0)
  n,s = 1,0
  while n!=N+1:
    if s==S+1: n,s = n+1,0
    else:
      tab[n][s] = tab[n-1][s]
      if tab[n][s]==False and a[n-1]<=s: tab[n][s] = tab[n-1][s-a[n-1]]
      s += 1
  return tab[N][S]