私のスキルで飯は食えるか？

Pythonで解きました。所要時間は１時間ぐらいだと思います（時間を測るのを忘れました）。

#encoding:shift-jis
from __future__ import division, print_function
__metaclass__ = type 
import re
from itertools import permutations, combinations

def removed(alist, x):
    alist = list(alist)
    alist.remove(x)
    return alist

def combinations2(iterable, r):
    """
    combinations2('ABCD', 2) --> (AB,CD) (AC,BD) (AD,BC) (BC,AD) (BD,AC) (AB,CD)
    >>> from itertools import combinations
    >>> i2 = s.combinations2("ABCDE", 2)
    >>> i1 = s.combinations("ABCDE", 2)
    >>> all(x == y for x, (y, _) in zip(i1, i2))
    True
    """
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            comb = tuple(pool[i] for i in indices)
            rest = tuple(pool[i] for i in xrange(n) if i not in indices)
            yield comb, rest
    
def is_pair(tiles):
    assert len(tiles) == 2
    return len(set(tiles)) == 1

def is_triple(tiles):
    assert len(tiles) == 3
    return len(set(tiles)) == 1

def is_seq(tiles):
    assert len(tiles) == 3
    tiles = sorted(tiles)
    return tiles[0] == (tiles[1] - 1) == (tiles[2] - 2)
    
def pop_body(tiles):
    """
    パイの中から、『体』になりうる３枚組を全て見つけ、
    ３枚組みとそれ以外を返します。
    """
    for comb, rest in combinations2(tiles, 3):
        if is_triple(comb) or is_seq(comb):
            yield comb, rest

def pop_head(tiles):
    """
    パイの中から、『頭』になりうる２枚組を全て見つけ、
    ２枚組みとそれ以外を返します。
    """
    for comb, rest in combinations2(tiles, 2):
        if is_pair(comb):
            yield comb, rest

def stuple(iterable, *a, **kw):
    return tuple(sorted(iterable, *a, **kw))

def split_tiles_3(tiles):
    """
    13 - 1 = 12 枚のパイを 3, 3, 3, 3 の体4つに分解する仕方を返します
    """
    bodies = set()
    add = bodies.add
    for t1, r1 in pop_body(tiles):
        for t2, r2 in pop_body(r1):
            for t3, r3 in pop_body(r2):
                for t4, r4 in pop_body(r3):
                    add(stuple([t1, t2, t3, t4]))
    return bodies

def split_tiles_2_3(tiles):
    """
    13 - 2 = 11 枚のパイを 2, 3, 3, 3 の頭1つと体4つに分解する仕方を返します
    """
    bodies = set()
    add = bodies.add
    for t1, r1 in pop_head(tiles):
        for t2, r2 in pop_body(r1):
            for t3, r3 in pop_body(r2):
                for t4, r4 in pop_body(r3):
                    add(stuple([t1, t2, t3, t4]))
    return bodies

def solv_1(tiles):
    """
    13枚の牌から「待ちの部分」が1枚になる、待ちを探します。
    """
    tiles = sorted(int(t) for t in tiles)
    for t in set(tiles):
        tiles1 = removed(tiles, t)
        for body in split_tiles_3(tiles1):
            yield (body, (t,))

def is_wait2(t):
    """
    「待ちの部分」になりうる２枚か判定します。
    すなわち、アンコかシュンツを作りうるか判定します。
    """
    assert len(t) == 2
    return (t[0] - t[1]) in [-2, -1, 0, 1, 2]

def solv_2(tiles):
    """
    13枚の牌から「待ちの部分」が2枚になる、待ちを探します。
    """
    tiles = sorted(int(t) for t in tiles)
    for t in set(combinations(tiles, 2)):
        if not is_wait2(t):
            continue
        tiles1 = removed(removed(tiles, t[0]), t[1])
        for body in split_tiles_2_3(tiles1):
            yield (body, t)

def solv(tiles):
    """すべての待ちをタプルで返す"""
    tiles = [int(t) for t in tiles]
    
    answers = []
    answers.extend(solv_1(tiles))
    answers.extend(solv_2(tiles))
    return answers

def solv_s(s):
    """回答を文字列で返す"""
    return [ans_to_str(ans) for ans in solv(s)]

def ans_to_str(ans):
    body, w = ans
    body = ["".join(map(str, t)) for t in body]
    w = "".join(map(str, w))
    return "({0[0]})({0[1]})({0[2]})({0[3]})[{1}]".format(body, w)

def str_to_ans(s):
    m = re.match("\((\d{2,3})\)\((\d{2,3})\)\((\d{2,3})\)\((\d{2,3})\)\[(\d{1,2})\]", s)
    bodies = stuple(stuple(int(d) for d in m.group(i)) for i in [1, 2,3,4])
    wait = stuple(int(d) for d in m.group(5))
    return (bodies, wait)

def answer_eq(ans1, ans2):
    return stuple(str_to_ans(ans) for ans in ans1) == stuple(str_to_ans(ans) for ans in ans2)

def test():
    assert answer_eq(solv_s("1112224588899"), ["(111)(222)(888)(99)[45]"])
    
    assert answer_eq(solv_s("1122335556799"), [
        "(123)(123)(555)(99)[67]",
        "(123)(123)(55)(567)[99]",
        "(123)(123)(99)(567)[55]",
    ])
    
    assert answer_eq(solv_s("1112223335559"), [
        "(123)(123)(123)(555)[9]",
        "(111)(222)(333)(555)[9]",
    ])
    
    assert len(solv_s("1223344888999")) == 3
    
    from pprint import pprint
    #九蓮宝燈は、すべての待ちを数えられなかったので、出力のみ
    pprint((solv_s("1112345678999")))
    
    
def main():
    test()

if "__main__" == __name__:
    main()

パソコンが修理中だったので、Pythonは久しぶりだったのですが、
一時HaskellやClojureの勉強をしたせいか、
listを非破壊的に操作する関数が無いことが窮屈に感じました。

上のコードで言えば、removedのような関数が標準で用意されていて欲しいです。

並行処理うんぬんのような、難しい意味では無くて、
単にリストを複製する必要がなくなり、コードが短くなるという意味ですが。