Big O of backtracking solution counts permutations with range

Question

I have a problem and I've been struggling with my solution time and space complexity:

Given an array of integers (possible duplicates) A and min, low, high are integers. Find the total number of combinations of items in A that:

• low <= A[i] <= high
• Each combination has at least min numbers.
• Numbers in one combination can be duplicates as they're considered unique in A but combinations can not be duplicates. E.g.: [1,1,2] -> combinations: [1,1],[1,2],[1,1,2] are ok but [1,1],[1,1], [1,2], [2,1] ... are not.

Example: A=[4, 6, 3, 13, 5, 10], min = 2, low = 3, high = 5

There are 4 ways to combine valid integers in A: [4,3],[4,5],[4,3,5],[3,5]

Here's my solution and it works:

class Solution:
    def __init__(self):
        pass
    def get_result(self, arr, min_size, low, high):
        return self._count_ways(arr, min_size, low, high, 0, 0)
    def _count_ways(self, arr, min_size, low, high, idx, comb_size):
        if idx == len(arr):
            return 0
        count = 0
        for i in range(idx, len(arr)):
            if arr[i] >= low and arr[i] <= high:
                comb_size += 1
                if comb_size >= min_size:
                    count += 1
                count += self._count_ways(arr, min_size, low, high, i + 1, comb_size)
                comb_size -= 1
        return count

I use backtracking so:

Time: O(n!) because for every single integer, I check with each and every single remaining one in worst case - when all integers can form combinations.

Space: O(n) for at most I need n calls on the call stack and I only use 2 variables to keep track of my combinations.

Is my analysis correct?

Also, a bit out of the scope but: Should I do some kind of memoization to improve it?

Answer 1

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