Input: nums = [0, -1, 2, -3, 1]
Output: [[-3, 1, 2], [-1, 0, 1]]

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

A brute force solution involves checking every possible triplet in the array to see if they sum to zero. This can be done using three nested loops, iterating through each combination of three elements.

Duplicate triplets can be avoided by sorting each triplet, which ensures that identical triplets with different representations (e.g., [1, 3, 2] and [3, 2, 1]) are ordered consistently (e.g., [1, 2, 3]). Once sorted, we can add these triplets to a hash set. This way, if the same triplet is encountered again, the hash set will only keep one instance. Below is the code snippet for this approach:

from typing import List
   
def triplet_sum_brute_force(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    # Use a hash set to ensure we don't add duplicate triplets.
    triplets = set()
    # Iterate through the indexes of all triplets.
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    # Sort the triplet before including it in the hash set.
                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    triplets.add(triplet)
    return [list(triplet) for triplet in triplets]

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<vector<int>> tripletSumBruteForce(vector<int>& nums) {
    int n = nums.size();
    set<vector<int>> seen;               // sorted triplets already recorded
    vector<vector<int>> result;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    vector<int> trip = {nums[i], nums[j], nums[k]};
                    sort(trip.begin(), trip.end());
                    if (seen.count(trip) == 0) {   // not recorded yet
                        seen.insert(trip);
                        result.push_back(trip);
                    }
                }
            }
        }
    }
    return result;
}

import java.util.*;

// This method lives inside a class, e.g. class Solution { ... }
public List<List<Integer>> tripletSumBruteForce(int[] nums) {
    int n = nums.length;
    Set<List<Integer>> seen = new HashSet<>();   // sorted triplets already recorded
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> trip = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k]));
                    Collections.sort(trip);
                    if (seen.add(trip)) {
                        result.add(trip);
                    }
                }
            }
        }
    }
    return result;
}

This solution is quite inefficient with a time complexity of $O(n^3)$, where $n$ denotes the length of the input array. How can we do better?

Let’s see if we can find at least one triplet that sums to 0. Notice that if we fix one of the numbers in a triplet, the problem can be reduced to finding the other two. This leads to the following observation:

For any triplet [a, b, c], if we fix 'a', we can focus on finding a pair [b, c] that sums to '-a' (a + b + c = 0 → b + c = -a).

Sound familiar? That's because the problem of finding a pair of numbers that sum to a target has already been addressed by Pair Sum - Sorted. However, we can only use that algorithm on a sorted array. So, the first thing we should do is sort the input. Consider the following example:

Now, starting at the first element, -2 (i.e., 'a'), we'll use the pair_sum_sorted method on the rest of the array to find a pair whose sum equals 2 (i.e., '-a'):

As you can see, when we called pair_sum_sorted, we did not find a pair with a sum of 2. This indicates that there are no triplets starting with -2 that add up to 0.

So, let's increment our main pointer, i, and try again.

This time, we found one pair that resulted in a valid triplet.

If we continue this process for the rest of the array, we find that [-1, -1, 2] is the only triplet whose sum is 0.

There’s an important difference between the pair_sum_sorted implementation in Pair Sum - Sorted and the one in this problem: for this problem, we don’t stop when we find one pair, we keep going until all target pairs are found.

Handling duplicate triplets
Something we previously glossed over is how to avoid adding duplicate triplets. There are two cases in which this happens. Consider the example below:

$\underline{\text{Case 1: duplicate ‘a’ values}}$

The first instance where duplicates may occur is when seeking pairs for triplets that start with the same ‘a’ value:

Since pair_sum_sorted would look for pairs that sum ‘-a’ in both instances, we’d naturally end up with the same pairs and, hence, the same triplets.

To avoid picking the same 'a' value, we keep increasing i (where num[i] represents the value 'a') until it reaches a different number from the previous one. We do this before we start looking for pairs using the pair_sum_sorted method. This logic works because the array is sorted, meaning equal numbers are next to each other. The code snippet for checking duplicate 'a' values looks like this:

# To prevent duplicate triplets, ensure 'a' is not a repeat of the previous element
# in the sorted array.
if i > 0 and nums[i] == nums[i - 1]:
    continue
... Find triplets ...

$\underline{\text{Case 2: duplicate ‘b’ values}}$

As for the second case, consider what happens during pair_sum_sorted when we encounter a similar issue. For a fixed target value (‘-a’), pairs that start with the same number ‘b’ will always be the same:

The remedy for this is the same as before: ensure the current ‘b’ value isn’t the same as the previous value.

It’s important to note that we don’t need to explicitly handle duplicate 'c' values. The adjustments made to avoid duplicate 'a' and 'b' values ensure each pair [a, b] is unique. Since 'c' is determined by the equation c = -(a + b), each unique [a, b] pair will result in a unique 'c' value. Therefore, by just avoiding duplicates in 'a' and 'b', we automatically avoid duplicates in the [a, b, c] triplets.

Optimization
An interesting observation is that triplets that sum to 0 cannot be formed using positive numbers alone. Therefore, we can stop trying to find triplets once we reach a positive ‘a’ value since this implies that ‘b’ and ‘c’ would also be positive.

Implementation

From the above intuition, we know we need to slightly modify the pair_sum_sorted function to avoid duplicate triplets. We also need to pass in a start value to indicate the beginning of the subarray on which we want to perform the pair-sum algorithm. Otherwise, the two-pointer logic remains nearly identical to that of Pair Sum - Sorted.

from typing import List
  
def triplet_sum(nums: List[int]) -> List[List[int]]:
    triplets = []
    nums.sort()
    for i in range(len(nums)):
        # Optimization: triplets consisting of only positive numbers will never sum
        # to 0.
        if nums[i] > 0:
            break
        # To avoid duplicate triplets, skip 'a' if it's the same as the previous
        # number.
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Find all pairs that sum to a target of '-a' ('-nums[i]').
        pairs = pair_sum_sorted_all_pairs(nums, i + 1, -nums[i])
        for pair in pairs:
            triplets.append([nums[i]] + pair)
    return triplets
  
def pair_sum_sorted_all_pairs(nums: List[int], start: int, target: int) -> List[int]:
    pairs = []
    left, right = start, len(nums) - 1
    while left < right:
        sum = nums[left] + nums[right]
        if sum == target:
            pairs.append([nums[left], nums[right]])
            left += 1 # To avoid duplicate '[b, c]' pairs, skip 'b' if it’s the same as the # previous number.
            while left < right and nums[left] == nums[left - 1]:
                left += 1
        elif sum < target:
            left += 1 
        else:
            right -= 1
    return pairs

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> tripletSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());       // step 1: sort ascending
    vector<vector<int>> triplets;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) break;           // 'a' positive: stop
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // skip repeated 'a'
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total == 0) {
                triplets.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++; // skip 'b'
            } else if (total < 0) {
                left++;                   // total too small: grow it
            } else {
                right--;                  // total too big: shrink it
            }
        }
    }
    return triplets;
}

import java.util.*;

// This method lives inside a class, e.g. class Solution { ... }
public List<List<Integer>> tripletSum(int[] nums) {
    Arrays.sort(nums);                    // step 1: sort ascending
    List<List<Integer>> triplets = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) break;           // 'a' positive: stop
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // skip repeated 'a'
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total == 0) {
                triplets.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++; // skip 'b'
            } else if (total < 0) {
                left++;                   // total too small: grow it
            } else {
                right--;                  // total too big: shrink it
            }
        }
    }
    return triplets;
}

Complexity Analysis

Time complexity: The time complexity of triplet_sum is $O(n^2)$. Here’s why:

• We first sort the array, which takes $O(n\log(n))$ time.
• Then, for each of the $n$ elements in the array, we call pair_sum_sorted_all_pairs at most once, which runs in $O(n)$ time.

Therefore, the overall time complexity is $O(\log(n))+O(n^2)=O(n^2)$.

Space complexity: The space complexity is $O(n)$ due to the space taken up by Python’s sorting algorithm. It's important to note that this complexity does not include the output array triplets because we’re only concerned with the additional space used by the algorithm, not the space needed for the output itself.

If the interviewer asks what the space complexity would be if we included the output array, it would be $O(n^2)$. This is because the pair_sum_sorted_all_pairs function, in the worst case, can add approximately $n$ pairs to the output. Since this function is called approximately $n$ times, the overall space complexity is $O(n^2)$.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Test Cases

In addition to the examples already covered in this explanation, below are some others to consider when testing your code.