@@ -0,0 +1,2413 @@
+from collections import defaultdict%0Aclass Solution(object):%0A    def dfs_ans(self, ans, depth, lans, ans_list):%0A        if depth == lans:%0A            yield ''.join(ans_list)%0A        else:%0A            if isinstance(ans%5Bdepth%5D, set):%0A                for x in ans%5Bdepth%5D:%0A                    ans_list.append(x)%0A                    for y in self.dfs_ans(ans, depth + 1, lans, ans_list):%0A                        yield y%0A                    ans_list.pop()%0A            else:%0A                ans_list.append(ans%5Bdepth%5D)%0A                for y in self.dfs_ans(ans, depth + 1, lans, ans_list):%0A                    yield y%0A                ans_list.pop()%0A%0A%0A    def dfs(self, dp, end, target, depth, cur, ans):%0A        if end == depth and cur == target:%0A            for x in self.dfs_ans(ans, 0, len(ans), %5B%5D):%0A                yield x%0A        else:%0A            for nd in xrange(depth + 1, end + 1):%0A                for possible_v, possible_set in dp%5Bdepth, nd%5D.iteritems():%0A                    if depth %3E 0:%0A                        ans.append('+')%0A                    ans.append(possible_set)%0A                    for x in self.dfs(dp, end, target, nd, cur + possible_v, ans):%0A                        yield x%0A                    ans.pop()%0A                    if depth %3E 0:%0A                        ans.pop()%0A                        for x in self.dfs(dp, end, target, nd, cur - possible_v, ans + %5B'-', possible_set%5D):%0A                            yield x%0A%0A    def addOperators(self, num, target):%0A        %22%22%22%0A        :type num: str%0A        :type target: int%0A        :rtype: List%5Bstr%5D%0A        %22%22%22%0A        dp = defaultdict(lambda:defaultdict(set))%0A%0A        # merge phase%0A        lnum = len(num)%0A        for i in xrange(1, lnum + 1):%0A            for j in xrange(i):%0A                if num%5Bj%5D != '0' or j + 1 == i:%0A                    dp%5Bj, i%5D%5Bint(num%5Bj:i%5D)%5D.add(num%5Bj:i%5D)%0A%0A        # multiple phase%0A        for l in xrange(2, lnum + 1):%0A            for i in xrange(lnum - l + 1):%0A                for j in xrange(i + 1, i + l):%0A                    for a, a_set in dp%5Bi, j%5D.iteritems():%0A                        for b, b_set in dp%5Bj, i + l%5D.iteritems():%0A                            for a_ in a_set:%0A                                if '*' not in a_:%0A                                    for b_ in b_set:%0A                                        dp%5Bi, i + l%5D%5Ba * b%5D.add(a_ + '*' + b_)%0A        return list(self.dfs(dp, lnum, target, 0, 0, %5B%5D))%0A

Add py solution for 282. Expression Add Operators