# 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 O(S) space solution

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