Untitled

How to find the Longest Common Subsequence in Exponential time?
def lcs(s1, s2):
 if len(s1)==0 or len(s2)==0: return 0
 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
 return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))

for i=n to 0
    for all length i subsequences s of a
        if s is a subsequence of b
            return s

def common_subsequences(A,B, len_subsequence_so_far = 0):
    if len(A) == 0 or len(B) == 0:
        return
    first_of_A = A[0] // the first letter in A.
    A1 = A[1:] // A, but with the first letter removed
    common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call
    if(the_first_letter_of_A_is_also_in_B):
        Bn = ... delete from the start of B up to, and including,
             ... the first letter which equals first_of_A
        common_subsequences(A1,Bn, 1+len_subsequence_so_far )