Big O of backtracking solution counts permutations with range

If I understand your requirements correctly, your algorithm is far too complicated. You can do it as follows:

1. Compute array B containing all elements in A between low and high.
2. Return sum of Choose(B.length, k) for k = min .. B.length, where Choose(n,k) is n(n-1)..(n-k+1)/k!.

Time and space complexities are O(n) if you use memoization to compute the numerators/denominators of the Choose function (e.g. if you have already computed 5*4*3, you only need one multiplication to compute 5*4*3*2 etc.).

In your example, you would get B = [4, 3, 5], so B.length = 3, and the result is

  Choose(3, 2) + Choose(3, 3) 
= (3 * 2)/(2 * 1) + (3 * 2 * 1)/(3 * 2 * 1) 
= 3 + 1
= 4