Additive Number

medium backtracking string

Problem

A string is additive if it can be split into a sequence of at least three numbers where every number equals the sum of the previous two. Numbers can't have leading zeros (except '0').

Inputnum = "112358"

Outputtrue

1, 1, 2, 3, 5, 8.

num (digit string)

def is_additive(num):
    n = len(num)
    for i in range(1, n // 2 + 1):
        if num[0] == "0" and i > 1: break
        for j in range(i + 1, n):
            if num[i] == "0" and j - i > 1: break
            a, b, k = num[:i], num[i:j], j
            while k < n:
                c = str(int(a) + int(b))
                if not num.startswith(c, k): break
                k += len(c); a, b = b, c
            if k == n: return True
    return False

function isAdditiveNumber(num) {
  const n = num.length;
  for (let i = 1; i <= n / 2; i++) {
    if (num[0] === "0" && i > 1) break;
    for (let j = i + 1; j < n; j++) {
      if (num[i] === "0" && j - i > 1) break;
      let a = num.slice(0, i), b = num.slice(i, j), k = j;
      while (k < n) {
        const c = String(BigInt(a) + BigInt(b));
        if (!num.startsWith(c, k)) break;
        k += c.length; [a, b] = [b, c];
      }
      if (k === n) return true;
    }
  }
  return false;
}

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i <= n / 2; i++) {
            if (num.charAt(0) == '0' && i > 1) break;
            for (int j = i + 1; j < n; j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;
                if (check(num.substring(0, i), num.substring(i, j), num, j)) return true;
            }
        }
        return false;
    }
    boolean check(String a, String b, String s, int k) {
        while (k < s.length()) {
            String c = new java.math.BigInteger(a).add(new java.math.BigInteger(b)).toString();
            if (!s.startsWith(c, k)) return false;
            k += c.length(); a = b; b = c;
        }
        return true;
    }
}

class Solution {
    string add(string a, string b) {
        string c; int i = a.size() - 1, j = b.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            int x = (i >= 0 ? a[i--] - '0' : 0) + (j >= 0 ? b[j--] - '0' : 0) + carry;
            c += char('0' + x % 10); carry = x / 10;
        }
        reverse(c.begin(), c.end()); return c;
    }
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        for (int i = 1; i <= n / 2; i++) {
            if (num[0] == '0' && i > 1) break;
            for (int j = i + 1; j < n; j++) {
                if (num[i] == '0' && j - i > 1) break;
                string a = num.substr(0, i), b = num.substr(i, j - i); int k = j;
                while (k < n) {
                    string c = add(a, b);
                    if (num.compare(k, c.size(), c) != 0) break;
                    k += c.size(); a = b; b = c;
                }
                if (k == n) return true;
            }
        }
        return false;
    }
};

Explanation

Once the first two numbers of the sequence are fixed, the entire rest is forced — each next number must equal the sum of the previous two. So we just try every possible first pair and let the chain verify itself.

The outer loops pick the length i of the first number and the end j of the second, giving a = num[:i] and b = num[i:j]. Leading-zero checks reject things like "05" (a multi-digit chunk can't start with 0).

Then a while loop builds forward: compute c = a + b as a string, and check the original keeps going with that exact substring using num.startswith(c, k). If it matches, advance the cursor k, slide a, b = b, c, and repeat.

If the cursor lands exactly at the end (k == n), the whole string was consumed by a valid additive chain, so we return true.

Example: "112358". First pair 1 and 1 gives 1+1=2, then 1+2=3, 2+3=5, 3+5=8 — the string is exactly 1,1,2,3,5,8, so the answer is true.

Time: O(n^3) Space: O(n)