In fact it is very very important that your values are between 1 and 100! Because with a vector of size 1,000,000 you have a lot of numbers that are equal and you don't need to inspect all of them! What you can do is the following:

Note: the following code is just an outline! It may lack sufficient error checking and is just here to give you the idea, not for copy paste!

Note2: When I wrote the answer, I assumed the numbers to be in the range [0, 99]. Then I read that they are actually in [1, 100]. Obviously this is not a problem and you can either -1 all the numbers or even better, change all the 100s to 101s.

```
bool exists[100] = {0}; // exists[i] means whether i exists in your vector
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
exists[vect[i]] = true;
```

Then, you do similar to what you did before:

```
for(unsigned int x = 0; x < 98; x++)
if (exists[x])
for(unsigned int y = x+1; y < 99; y++)
if (exists[y])
for(unsigned int z = y+1; z < 100; z++)
if (exists[z])
{
// {x, y, z} is an answer
}
```

Another thing you can do is spend more time in preparation to have less time generating the pairs. For example:

```
int nums[100]; // from 0 to count are the numbers you have
int count = 0;
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
bool exists = false;
for (int j = 0; j < count; ++j)
if (vect[i] == nums[j])
{
exists = true;
break;
}
if (!exists)
nums[count++] = vect[i];
}
```

Then

```
for(unsigned int x = 0; x < count-2; x++)
for(unsigned int y = x+1; y < count-1; y++)
for(unsigned int z = y+1; z < count; z++)
{
// {nums[x], nums[y], nums[z]} is an answer
}
```

Let us consider 100 to be a variable, so let's call it `k`

, and the actual numbers present in the array as `m`

(which is smaller than or equal to `k`

).

With the first method, you have `O(n)`

preparation and `O(m^2*k)`

operations to search for the value which is quite fast.

In the second method, you have `O(nm)`

preparation and `O(m^3)`

for generation of the values. Given your values for `n`

and `m`

, the preparation takes too long.

You could actually merge the two methods to get the best of both worlds, so something like this:

```
int nums[100]; // from 0 to count are the numbers you have
int count = 0;
bool exists[100] = {0}; // exists[i] means whether i exists in your vector
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
if (!exists[vect[i]])
nums[count++] = vect[i];
exists[vect[i]] = true;
}
```

Then:

```
for(unsigned int x = 0; x < count-2; x++)
for(unsigned int y = x+1; y < count-1; y++)
for(unsigned int z = y+1; z < count; z++)
{
// {nums[x], nums[y], nums[z]} is an answer
}
```

This method has `O(n)`

preparation and `O(m^3)`

cost to find the unique triplets.

**Edit:** It turned out that for the OP, the same number in different locations are considered different values. If that is really the case, then I'm sorry, there is no faster solution. The reason is that all the possible combinations themselves are `C(n, m)`

(That's a combination) that although you are generating each one of them in `O(1)`

, it is still too big for you.

`1[0] 5[1] 7[2] and 1[3] 5[1] 7[4] are diferent`

Are you absolutely, 100% certain about that? If so, then you cannot get more optimal (in a single thread).1more comment