Unique Combinations

I came across a Leetcode problem: 15. 3Sum. Here is the problem description:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

One of the main problems I approached when doing this was figuring out how to avoid duplicate triplets. It’s simple in hindsight, however, I just could not wrap my head around why the solution works.

Let’s dumb down the problem to finding unique pairs of two. Given the following set, {0, 1, 2} we can start with 0 and check every number after 0 to find unique pairs—{0, 1} and {0, 2}. After that, we can safely assume no other pairs with 0 exist, so we’ll remove that from our view and repeat the process with 1 and check every number after 1 giving us the pair {1, 2}. Now can we remove 1 from our view and move on to 2. However, there are no numbers after 2 so there is nothing to check here.

Let’s extrapolate that process into a procedure. We’ll have a fixed index to mark the beginning of a search i starting at 0. For each instance of i, we’ll grab any values (which we’ll index as j) after i to form our pairs. In other words, any j where j > i guarantees us a unique pair. Then we can increment i and repeat the process. But when do we stop incrementing i? We don’t need to go to the very end, only to n - 1 because a pair requires two numbers.

Okay, so let’s upgrade this to the original problem with triplets. It turns out to be the exact same process, but done twice! We’ll have 3 indexes this time: i, j, k. We’ll fix i to 0, and we have now simplified the problem to finding unique pairs of two just as we did before. So we’ll fix j to 1 and search for every number after 1, which is k. Once we finish this procedure, we’ll have ruled out 0 as a possible combination and can now fix i to 1, and repeat. In other words, k > j > i is our new constraint. This time, we only want i to go to n - 2 because the search requires at least 3 numbers.

And so on! The main idea here is that by starting with a number and doing every combination from that point, we can rule out that number from future combinations.

Given the following set, {0, 1, 2, 3}, let’s find determine each permutation, and cross out any duplicate combinations.

Some Theory

This is ultimately a problem of combinatorics, particularly regarding the distinction between permutations and combinations.

1. Permutations = Unique orderings

• You’re counting arrangements, where order matters.
• Example: {A, B, C} → all of:
  • ABC, ACB, BAC, BCA, CAB, CBA (6 total)

2. Combinations = Unique groups

• You’re counting subsets, where order doesn’t matter.
• Example: {A, B, C} → only:
  • {A, B, C}