aabb.py

from __future__ import print_function

# The recursive relation is
# f(0) = ''
# f(n) = [s + 'a' for s in f(n - 1)] + [s + 'b' for s in f(n - 1)]

def allABs1(N):
    if N <= 0:
        return ['']
    res = []
    for s in allABs1(N - 1):
        res.append(s + 'a')
        res.append(s + 'b')
    return res


# DFS solution, faster and less memory consumption
def allABs2(N):
    res = []
    def helper(s):
        if len(s) == N:
            res.append(s)
        else:
            helper(s + 'a')
            helper(s + 'b')
    helper('')
    return res


def test(N):
    print('All such strings with length ' + str(N))
    print('Naive recursion:', allABs1(N))
    print('DFS:', allABs2(N))
    print()


if __name__ == '__main__':
    for i in range(5):
        test(i)