K product array

Question

I am working on an algorithms problem. You have an array numbers, size of array t , number number_of_elements and number multiplication_value. You have to find any set of number_of_elements indexes of the elements of the array , which product will be equal to multiplication_value. It is guaranteed, that such set of indexes exists

That problem looks like 2 sum, but I can't extrapolate it to my case. I have tried naive algorithm for O(n), but it fails, when you have bad first number in an array. I think there is a way to use recursion in here. I guess it is well-known problem, but I couldn't find the solution

Example in:

t = 7
number_of_elements = 2
multiplication_value = 27
numbers = [9,1,1,27,3,27,3]

Example out:

1 3

My code ideas:

    def return_index_values(numbers,multiplication_value,number_of_elements):
    cur_number = int(multiplication_value)
    list_of_indexes = []
    values = []
    for i in range(len(numbers)):
        if ((cur_number == 1) and (len(values) == number_of_elements)):
            print(values)
            #finishing if everything worked
            break
        else:               
            if (cur_number % int(numbers[i]) == 0):
                if(len(values) < number_of_elements):
            #pushing values if possible
                    values.append(int(numbers[i]))
                    list_of_indexes.append(i)
                    cur_number = int(cur_number / int(numbers[i]))
                    print(cur_number)
                else:
                    pass
            if(len(values) == number_of_elements):
                if mult_check(values,int(multiplication_value)):
               #mult_check checks if the array's element multiplication gives a value
                    break
                else:
               #started dealing with bad cases, but it doesn't work properly
                    values.sort()
                    val_popped = values.pop()
                    cur_number = cur_number * val_popped 

Bad case for my code

 numbers = [9,3,1,27,3,27,3]

Answer 1

Here is one implementation. Not necessarily the best solution but it gives you some sense of how it can be done.

It first sorts the numbers by the element keeping the indices information. Then it performs recursion calls.

number_of_elements = 2
multiplication_value = 27
numbers = [9,1,1,27,3,27,3]

def preprocess(numbers, multiplication_value, number_of_elements):
    l = []
    for i, num in enumerate(numbers):
        l.append((num, i))
    return sorted(l, key = lambda tup: tup[0])

def subroutine(numbers, multiplication_value, number_of_elements, idx_start, result):
    if idx_start >= len(numbers):
        return False
    if number_of_elements == 0:
        return True if multiplication_value == 1 else False
    for i in range(idx_start, len(numbers)):
        num = numbers[i][0]
        if num <= multiplication_value:
            if multiplication_value % num == 0:
                idx = numbers[i][1]
                result.append(idx)
                found = subroutine(numbers, multiplication_value / num, number_of_elements - 1, i + 1, result)
                if not found:
                    del result[-1]
                else:
                    return True
        else:
            return False
    return False

result = []
processed_numbers = preprocess(numbers, multiplication_value, number_of_elements)
subroutine(processed_numbers, multiplication_value, number_of_elements, 0, result)
print(result)