Formula to Find All Possible Variations I've been trying to solve a coding problem for several days now and I'm fairly stuck and I'll blame this on my inferior knowledge of math.  I've been trying to do this by iterating over each number, finding the differences, and listing each iteration; however, this is proving to be incredibly complicated as well as non-performant.

Given a monotonic array of numbers, count the number of variations that can exist between these numbers where the distance can be 1, 2, or 3.

So if I have a list of numbers:
   1,  2,  3,  4,  7,  8,  9, 10, 11,
  14, 17, 18, 19, 20, 23, 24, 25, 28,
  31, 32, 33, 34, 35, 38, 39, 42, 45,
  46, 47, 48, 49

If I were to list out each number that can have a variation and the distance between it and the next number I would get a list like:
// num => paths: [...distance to next number]
  1 => [ 1, 2, 3 ],
  2 => [ 1, 2 ],
  7 => [ 1, 2, 3 ],
  8 => [ 1, 2, 3 ],
  9 => [ 1, 2 ],
  17 => [ 1, 2, 3 ],
  18 => [ 1, 2 ],
  23 => [ 1, 2 ],
  31 => [ 1, 2, 3 ],
  32 => [ 1, 2, 3 ],
  33 => [ 1, 2 ],
  45 => [ 1, 2, 3 ],
  46 => [ 1, 2, 3 ],
  47 => [ 1, 2 ]

I'm fairly certain there is a way that I can use the list above to grab the different variations that would exist.  An example of a particular variation would be:
1,4,7,10,11,14,17,19,20,23,25,28,31,34,35,38,39,42,45,48,49
A couple of other takeaways:

*

*The order of the numbers must remain in a monotonic pattern.

*I know that this particular list has a possible of number of variations of 19208.

*The distance between one number and the next cannot be greater than 3
 A: It seems like the question has an extra condition that the first number must be less than or equal to $3$ and the last number must be the largest number in the set, based on the two test cases given with results $19208$ and $8$,
Here's how you find the number:
#include <iostream>

using namespace std;

int num = 0;
void traverse(int* list, int size, int i) {
    if(i >= size) {
        return;
    }

    if(i == size - 1) {
        num ++;
        return;
    }
    if(i <= size - 2 && list[i+1] - list[i] <= 3) {
        traverse(list,size,i+1);
    }
    if(i <= size - 3 && list[i+2] - list[i] <= 3) {
        traverse(list,size,i+2);
    }
    if(i <= size - 4 && list[i+3] - list[i] <= 3) {
        traverse(list,size,i+3);
    }
}

int main()
{
    int arr[]= {1,  2,  3,  4,  7,  8,  9, 10, 11,
  14, 17, 18, 19, 20, 23, 24, 25, 28,
  31, 32, 33, 34, 35, 38, 39, 42, 45,
  46, 47, 48, 49};
    int size = 31;

    for(int i = 0; i < size; i ++) {
        if(arr[i] > 3) break;
        traverse(arr,size,i);
    }
    cout << num;
    return 0;
}

You can paste it here and test (modify the arr and size parts to change the array): https://www.onlinegdb.com/online_c++_compiler
DP-optimized way of the above algorithm (In order to deal with the "first number must be less than or equal to three" constraint you will need to add a zero at the beginning of the array and increase size by 1):
#include <iostream>

using namespace std;

int main()
{
    int arr[]= {0,  1,  2,  3,  4,  7,  8,  9, 10, 11,
  14, 17, 18, 19, 20, 23, 24, 25, 28,
  31, 32, 33, 34, 35, 38, 39, 42, 45,
  46, 47, 48, 49};
    int size = 32;
  
    int* nums = new int[size];
    for (int i = 0; i < size; i ++) {
        nums[i] = 0;
   }
    nums[0] = 1;
    for (int i = 0; i < size; i ++) {
        if(i >= 3 && arr[i] - arr[i - 3] <= 3) {
            nums[i] += nums[i - 3];
        }
        if(i >= 2 && arr[i] - arr[i - 2] <= 3) {
            nums[i] += nums[i - 2];
        }
        if(i >= 1 && arr[i] - arr[i - 1] <= 3) {
            nums[i] += nums[i - 1];
        }
    }

    cout << nums[size - 1];
    return 0;
}

