306. Additive Number

迭代回溯法， 用两个指针来切割字符串，将字符串分为三个部分，前两部分作为第一个数字和第二个数字，计算他们的和，作为result， 然后在第三部分查找是否以result开头，用startswith()函数判断。如果不是就剪掉，也就是break，如果是，second 变成新的first， third中result部分变成新的second， 剩下变成third，循环下去，判断一下最后third是不是到字符串末尾了，如果到了，return true

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        if num == None or len(num) < 3:
            return False
        for i in range(1, n/2+1):
            if i > 1 and num[0] == '0':
                break
            for j in range(i+1, (i+n)/2 + 1):
                if j > i+1 and num[i] == '0':
                    break
                first, second, third = 0, i, j
                while third < n:
                    first_num = int(num[first:second])
                    second_num = int(num[second:third])
                    result = first_num + second_num
                    if num[third:].startswith(str(result)):
                        first, second, third = second, third, third + len(str(result))
                    else:
                        break
                if third == n:
                    return True
        return False

另一种写法，combinations(iterable,r);创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        for i, j in itertools.combinations(range(1, n), 2):
            print i, j
            a, b = num[:i], num[i:j]
            if b != str(int(b)):
                continue
            while j < n:
                c = str(int(a) + int(b))
                if not num.startswith(c, j):
                    break
                j += len(c)
                a, b = b, c
            if j == n:
                return True
        return False