How do you approach Additive Number?

Fix the first two numbers by trying all split points; the rest is forced.

What are common mistakes on Additive Number?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

Sitelet https://gitgood.dev/coding/additive-number

gitGood.dev

← Back to problems

Additive Number

MediumAlgorithms

Description

A string is an additive number if its digits can form an additive sequence: it must contain at least three numbers where, after the first two, each number equals the sum of the previous two. Numbers may not have leading zeros (except the single digit 0).

Given a string num of digits, return true if it is an additive number.

Example 1

Input: num = "112358"

Output: true

Explanation: 1, 1, 2, 3, 5, 8.

Example 2

Input: num = "199100199"

Output: true

Explanation: 1, 99, 100, 199.

Constraints

- 1 <= num.length <= 35 - num consists only of digits

Additive Number: approach, complexity and pitfalls

A medium backtracking problem, graded against 9 test cases (7 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

Fix the first two numbers by trying all split points; the rest is forced.
Use string addition to avoid overflow on long inputs, and reject leading zeros.

The optimal approach

Show the approach: The approach

Try all first/second splits. Enumerate the lengths of the first two numbers; the remainder is then forced: repeatedly compute the next sum and check it prefixes the rest. Use string addition so large numbers don't overflow.

Time: O(n³). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

Additive Number

MediumAlgorithms

Description

Given a string num of digits, return true if it is an additive number.

Example 1

Input: num = "112358"

Output: true

Explanation: 1, 1, 2, 3, 5, 8.

Example 2

Input: num = "199100199"

Output: true

Explanation: 1, 99, 100, 199.

Constraints

- 1 <= num.length <= 35 - num consists only of digits

Additive Number: approach, complexity and pitfalls

A medium backtracking problem, graded against 9 test cases (7 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

Fix the first two numbers by trying all split points; the rest is forced.
Use string addition to avoid overflow on long inputs, and reject leading zeros.

The optimal approach

Show the approach: The approach

Time: O(n³). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.