LeetCode 306: Additive Number Solution

Master LeetCode problem 306 (Additive Number), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

306. Additive Number

Medium

String Backtracking

Problem Explanation

Explanation:

To solve this problem, we can use a recursive approach where we try all possible combinations of the first two numbers and check if the rest of the string forms a valid additive sequence. We can keep track of the current numbers being considered and recursively check if the next number in the sequence is valid.

Algorithm:

Start by iterating through all possible combinations of the first two numbers (i, j) where i ranges from 1 to num.length/2.
For each pair (i, j), convert the substrings num[0...i] and num[i...j] to long integers and check if they have leading zeros.
If the first two numbers are valid, check if the rest of the string forms a valid additive sequence recursively.
In the recursive function, keep track of the current number (sum) formed by the previous two numbers and try to match it with the current prefix in the string.
If the current prefix matches the sum, recursively check the rest of the string starting from the next index.
If we reach the end of the string and all numbers form a valid additive sequence, return true. Otherwise, return false.

Time Complexity: O(n^3) where n is the length of the input string num. Space Complexity: O(n) for the recursive call stack.

Solution Code

class Solution {
    public boolean isAdditiveNumber(String num) {
        return isAdditiveNumberHelper(num, 0, 0, 0, 0);
    }

    private boolean isAdditiveNumberHelper(String num, int idx, long num1, long num2, int count) {
        if (idx == num.length()) {
            return count >= 3;
        }

        for (int i = idx; i < num.length(); i++) {
            if (i > idx && num.charAt(idx) == '0') break;
            long current = Long.parseLong(num.substring(idx, i + 1));
            if (count < 2 || current == num1 + num2) {
                if (isAdditiveNumberHelper(num, i + 1, num2, current, count + 1)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 306 (Additive Number)?

This page provides optimized solutions for LeetCode problem 306 (Additive Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 306 (Additive Number)?

The time complexity for LeetCode 306 (Additive Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 306 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 306 in Java, C++, or Python.

Back to LeetCode Solutions