Additive Sequence Algorithm

Question

I am practicing algorithms for interviews and came across this question on Career Cup and SO An additive sequence number is which when splitted in two different number forms additive seq.

Ex: 1235 (split it 1,2,3,5) Ex: 12122436(split 12,12,24,36) given a range find all additive seq numbers ?

Below is what I tried, I know it is not efficient and not sure about its complexity. Also, It does not find numbers like 53811 and 12122436 which I am interested in finding. I will be really thankful if someone can guide me in right directions or come up with something more simple and efficient. Thanks!

#include <stdio.h>

void check_two_num_sum(int,int);
void check_sum(int);
int flag = 0;

int main(){

int high,low;
printf("Enter higher range\n");
scanf("%d",&high);
printf("Enter lower range\n");
scanf("%d",&low);
check_two_num_sum(high,low);

return 0;
}

void check_two_num_sum(int high, int low)
{
  flag=0;
  for(low;low<high;low++)
  {
    check_sum(low);  
    if(flag==1)
    {
       printf("this value has additive sequence %d \n",low);
       flag = 0; 
     }
  }
}

void check_sum(int input)
{
   int count = 1;
   int capture, result, temp_res=0, n=0;

   if(n==0){
    result = input%10;
        n++;
        input = input/10;
        capture = input;
    }

   while(input!=0)
   {
     temp_res = temp_res + input%10;    

     if(count ==2)
      {
         if(result == temp_res)
          { 
         if(capture < 100)
        {       flag = 1;
                    break; 
        }

         else{
              check_sum(capture);
        }
           }

          else {
          break;
        }
        } 
    count++;
    input = input/10;
  }
}

Answer 1

I'm not sure how efficient it would be, but I might try something recursive.

For example, 53811

Point to the end of the string, say.

Var2 = 1
Var1 = 1

Check if Var0 equals Var2 - Var1

1 - 1 does not equal 8, so this strand of the function is terminated.

In the next strand of the function, Var2 equals the last two digits, 11; Var1 = 8

Check if Var0 equals Var2 - Var1

11 - 8 equals 3 so this strand of the function continues: Var2 = 8; Var1 = 3

Check if Var0 equals Var2 - Var1

8 - 3 equals 5 and this is also the end of the string so the function returns True

The base case seems to be if the pointer is at the beginning of the string or no viable variables could be tested. At each junction point, Var2 and Var1 would be altered accordingly to start a new strand; Var0 is deduced from the other two.