Dynamic programming: find the subset with product of all members is equals to given number

Question

I will find an algorithm for this problem.

Input: array of n integers and number k

We must find a set of numbers from array, that product of all this numbers in set equals to k is

I think, I must use dynamic programming for this task. But I have no idea, how to use it.

Answer 1

This is similar to the subset sum problem, where you are required to find a subset whom sum is a value k.

Since there is a solution to your problem (you have a subset S whom multiplication is k) if and only if you have a subset of log(x) for each x in the set, whom sum is log(k) (the same subset, with log on each element), the problems are pretty much identical.

However, the DP solution generally used is very efficient for sums, since sum of elements don't tend to end up huge, while multiplying does. You also cannot take log on all elements and "work with it", because the numbers will not be integers - and the DP solution to subset sum requires integers to work on.

However, you can partially solve this issue by using Top-Down DP (memoization). This is fairly simple and is done as follows:

existenceOfSubset(set, product, map):
    if (product== 1):
           return true
    if (set.isEmpty()):
           return false
    if (map.containsKey(product)):
           return map.get(product)
    first = set.getFirst()
    set = set.removeFirst()
    solution = existenceOfSubset(set,product,map) OR (product%first == 0?existenceOfSubset(set,product/first,map):false) //recursive step for two possibilities
    map.put(product,solution  //memoize
    set.addFirst(first) //clean up
    return solution

invoke with existenceOfSubset(set,product,new HashMap())