Count all subsequences in an array with product less than K

Finding subsequences in an array with product less than a given number is another area of application of Dynamic programming. Our aim is to find the combinations of elements that when multiplied give the product less than an arbitrary number K. We can either go about it by brute-forcing through all the elements which will require a lot of time and calculations, or we can make use of dynamic programming to break this down into smaller sub-problems and use the result of each to build up to our solution.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/count-all-subsequences-in-array-with-product-less-than-k/
1 Like

It was really very very helpful

Correcting the array:
[0, 0, 0, 0, 0]
[0, 1, 1, 1, 1]
[0, 1, 3, 3, 3]
[0, 1, 3, 5, 5]
[0, 1, 3, 5, 7]
[0, 1, 3, 5, 7]
[0, 1, 3, 7, 9]
[0, 1, 3, 7, 9]
[0, 1, 3, 7, 11]
[0, 1, 3, 7, 11]
[0, 1, 3, 7, 11]