Python backtracking solution in 20 lines

  • 0

    The idea is to maintain a seq array to contain the additive sequences, and write a function dfs(i) which aims at finding a (valid) new subseq starting at position i of input string.

    def isAdditiveNumber(self, num):
        seq = []
        def dfs(i):# seleceting new subseq starting from position i of string `num`
            if i>=len(num): return len(seq)>=3 # seq should have >=3 numbers!
            for j in xrange(i,len(num)): # check all splitting possibilities [i,j]
                if num[i]=='0' and j>i: break # no leading zeros
                nb = int(num[i:j+1]) # subseq [i,j]
                if len(seq)<2: # if this is for the first 2 subseqs: no need to check sum
                    if dfs(j+1): return True
                    else: seq.pop() # backtracking
                    if nb==seq[-1]+seq[-2]:
                        seq.append(nb) # this current subseq is OK
                        if dfs(j+1): return True
                        else: seq.pop()
            return False 
        return dfs(0)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.