Task — Additive number

You are given a string containing digits 0-9 only. Write a script to find out if the given string is an additive number. An additive number is a string whose digits can form an additive sequence. A valid additive sequence should contain at least 3 numbers. Except the first 2 numbers, each subsequent number in the sequence must be the sum of the preceding two.

Analysis

This is another challenge that can be solved by recursion, or maybe a stack-based method which avoids recursion per se. However, as we shall see, the maximum depth of recursion is limited to the number of digits in string, and in most cases is much less. Moreover, we are not required to find the best solution (for some value of 'best') but merely a solution - though I have not pondered the question of whether it's possible to create a string which can be parsed as additive more than one way .

At each step in the process we take successively the first 1, 2, 3 .. all of the (remaining) digits in $string, and see if the number thus composed is additive with respect to any numbers already in our array of additive numbers. We don't need to make an additivity test on the first two numbers, as any 2 numbers could potentially start an additive series. If we have success in finding additivity we add the new number to our array and take its digits away from $string. And if that leaves $string empty we have a solution and can stop.

The challenge is silent on the subject of leading zeroes, so I have assumed that they are allowed, and so for example 1002003 is additive as 1 + 002 = 003.

Because of the factors mentioned above, this algorithm handles a 40 member series in milliseconds, but that gets close to bigint territory, where we shall not pursue it.

Try it 

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-07-03
use utf8;     # Week 224 task 2 - Additive number
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my ($solution, @string, $j);

additive_number('12354782');
additive_number('199100199299498');
additive_number('0030047');
additive_number('314159');

# create a long one
@string = (28,74);;
for $j (0 .. 19) {
    push @string, $string[-1] + $string[-2];
}
additive_number(join('', @string));

sub additive_number {
    
    my $string;
    
    # initialise
    $solution = '';
    $string = shift @_;
    
    # start recursion
    test([], $string);
    
    # results
    say qq[\nInput:  \$string = '$string'];
    say qq[Output: ] . ($solution ? $solution : 'false');
}

sub test {
    
    # test 1 further number (maybe several digits) along $string
    
    my (@numbers, $string, $count, $length, $j, @new_numbers, $new_string, $keep_going);
    
    # we can stop if a solution has been found
    return if $solution;
    
    # initialise
    @numbers = @{$_[0]};
    $string = $_[1];
    $count = scalar @numbers;
    
    # if we have only 1 or 2 numbers they must be valid and we don't need to test them
    if ($count < 3) {
        $keep_going = 1;
    
    # we check that the last 3 numbers are additive, and if the string is now empty we have a solution
    } else {
        $keep_going = $numbers[-3] + $numbers[-2] == $numbers[-1];
        if ($keep_going and $string eq '') {
            $solution = join(', ', @numbers);
            return;
        }
    }
    
    # $keep_going is true if the sequence of @numbers is good but incomplete
    return unless $keep_going;
    
    # try using the next 1, 2, 3 ... digits from $string
    $length = length($string);
    for $j (1 .. $length) {
        @new_numbers = (@numbers, substr($string, 0, $j));
        $new_string = $j == $length ? '' : substr($string, $j);
        
        # and recurse with those
        test(\@new_numbers, $new_string);
    }
}

Output

Input:  $string = '12354782'
Output: 12, 35, 47, 82

Input:  $string = '199100199299498'
Output: 1, 99, 100, 199, 299, 498

Input:  $string = '0030047'
Output: 003, 004, 7

Input:  $string = '314159'
Output: false

Input:  $string = '2874102176278454732118619183104502281261314821274344225569690118145814235932381746617678999424'
Output: 28, 74, 102, 176, 278, 454, 732, 1186, 1918, 3104, 5022, 8126, 13148, 21274, 34422, 55696, 90118, 145814, 235932, 381746, 617678, 999424