Backtracking: Get the sequential digits from the given range

Problem Statement:

You are given 2 values, low, high. You need to find the sequential digits, where one number is more than the previous digit.

You need to return the result in sorted order.

Example

Input: low = 100, high = 300

Output: [123,234]

Solution

We will use backtracking in the solution.

We need the integers from 1 to 9. We dont consider 0 as it is the smallest.

So for every digit from 1 to 10, we call the backtracking function that will check if there is a sequence number and if it is there, then it will put it in the result.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<vector>
#include<set>

using namespace std;


vector<int> res;

void backtrack(int low,int high,int curr_num,int index)
{
  if(curr_num>=low && curr_num<=high){
      res.push_back(curr_num);
  }
  if(index == 10 || curr_num >= high)
      return;
  backtrack(low, high, curr_num*10+index, index+1);
}

vector<int> get_sequential_digits(int low, int high) 
{
  for(int i=1; i<10; i++)
   backtrack(low,high,0,i);

  sort(res.begin(),res.end());
  return res;
}


int main()
{

   get_sequential_digits(1000, 14000);
   cout<<"Result = "<<endl;
   for (int i = 0; i < res.size(); i++)
    {
      cout<<res[i]<<" ";
    }


    return 0;
}

Output:

1234 2345 3456 4567 5678 6789 12345