## Introduction

In this article, we will learn to solve the problem of subsets with products less than K. Array-based questions are the most popular in coding interviews and programming competitions. We will see the problem from different angles and analyze it to reach the optimal solution eventually.

Let's get started with the problem statement.

Also Read About, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

Given an array of n elements, determine the number of subsets with a product of elements less than a given integer k.

Before proceeding the with the approach, we need to understand what the subset of the array means:

Subset is all the possible combinations of the array using each element (including phi) which means no array elements.

Subsets may not be contiguous and may not be in order.

Example - {2, 5, 3, 9}

Possible subsets- {}, {2}, {5}, {3}, {9}, {2,5} {2,3}, {2,9}, {5,3}, {5,9}, {3,9}, {2,5,3}, {2,5,9}, {2,3,9}, {5,3,9}, {2,5,3,9}.

An array's number of subsets is 2^N, where N is the array's Size.

### Sample Example

```
Input : arr[] = {2, 3, 5, 1, 6}, k = 11
Output :Number of subsets with product less than k:10
Explanation : All possible number subsets with
product less than k are:
(2), (3), (5), (1), (6), (2, 3), (2, 5), (2, 1), (3, 1), (5,1), (1,6), (2,3,1), (2,5,1)
Input : arr[] = {13, 42, 11 }, k = 1
Output : Number of subsets with product less than k: 0
Explanation : there is no possible subset such
that product of elements of each subset is less than 1
```

## Brute Force Approach

This is the most straightforward approach for this problem: find all the subsets of the array, check their product, and count those subsets with products less than k.

Then print the count.

### Pseudocode

- Generate all the subsets of the array and a count variable set to 0.

- For each subset, calculate the product of its elements and check whether the product is less than k or not. If yes, then increment the count.
- Return the count.

### Implementation in C++

```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int Subsets_with_product_less_than_k(vector < ll > & vect, int n, long long int k) {
int count = 0;
//generating all the subsets
for (int i = 0; i < (1 << n); i++) {
long long value = 1;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
value *= vect[j];
}
}
// counting the subset with product less than k and excluding empty //subset
if (value < k && i != 0)
count++;
}
return count;
}
int main() {
vector < long long int > vect { 2, 3, 5, 1, 6 };
int n = vect.size();
long long int k = 25;
cout << "Number of Subsets with product less than k: " << Subsets_with_product_less_than_k(vect, n, k);
return 0;
}
```

**Output:**

`Number of Subsets with product less than k: 13`

#### Complexity Analysis

**Time complexity:** O(n*2^{n}) because we have to generate all possible 2^{n} subsets, and for each of them, we have to calculate the product of elements of the subset and compare the value of the product with the given value of K.

N = Size of the array.

**Space Complexity: **O(1)

No extra space is used.