Three Sum Problem All Unique Triplets in DSA C++

Mental Model

Find three numbers in a list that add up to zero without repeating any triplet.

Analogy: Imagine you have a group of friends with different amounts of money. You want to find three friends whose combined money adds up to zero, like balancing a small group budget exactly.

nums: [-4] -> [-1] -> [-1] -> [0] -> [1] -> [2] -> null
indexes: 0     1      2      3     4     5

Dry Run Walkthrough

Input: list: [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the list to organize numbers

[-4, -1, -1, 0, 1, 2]

Why: Sorting helps to use two pointers efficiently and avoid duplicates

Step 2: Fix first number at index 0 (-4), set left=1, right=5

fixed=-4, left=-1, right=2

Why: Start searching pairs that sum with -4 to zero

Step 3: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

fixed=-4, left=-1 (index 2), right=2

Why: Sum too small, increase left to get bigger sum

Step 4: Sum = -4 + (-1) + 2 = -3 < 0, move left pointer right

fixed=-4, left=0 (index 3), right=2

Why: Still too small, move left pointer

Step 5: Sum = -4 + 0 + 2 = -2 < 0, move left pointer right

fixed=-4, left=1 (index 4), right=2

Why: Sum less than zero, move left pointer

Step 6: Sum = -4 + 1 + 2 = -1 < 0, move left pointer right

fixed=-4, left=2 (index 5), right=2

Why: Left pointer met right, no triplet with fixed -4

Step 7: Fix first number at index 1 (-1), set left=2, right=5

fixed=-1, left=-1, right=2

Why: Try next fixed number to find triplets

Step 8: Sum = -1 + (-1) + 2 = 0, record triplet [-1, -1, 2], move left and right skipping duplicates

triplets: [[-1, -1, 2]]; left=3, right=4

Why: Found valid triplet, move pointers to find others

Step 9: Sum = -1 + 0 + 1 = 0, record triplet [-1, 0, 1], move left and right

triplets: [[-1, -1, 2], [-1, 0, 1]]; left=4, right=3

Why: Found another triplet, pointers crossed, move to next fixed

Step 10: Fix first number at index 2 (-1), skip because same as previous fixed

skip fixed=-1 at index 2

Why: Avoid duplicate triplets by skipping same fixed number

Step 11: Fix first number at index 3 (0), set left=4, right=5

fixed=0, left=4, right=5

Why: Try next fixed number

Step 12: Sum = 0 + 1 + 2 = 3 > 0, move right pointer left

fixed=0, left=4, right=4

Why: Sum too big, decrease right pointer

Step 13: Left pointer met right, no triplet with fixed 0

end fixed=0

Why: No more pairs to check

Result:

[-1, -1, 2] -> [-1, 0, 1]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate fixed
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                // skip duplicates for left
                while (left < right && nums[left] == nums[left + 1]) left++;
                // skip duplicates for right
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> triplets = threeSum(nums);
    for (auto& triplet : triplets) {
        cout << "[" << triplet[0] << ", " << triplet[1] << ", " << triplet[2] << "]\n";
    }
    return 0;
}

sort(nums.begin(), nums.end());

sort input to enable two-pointer search and duplicate skipping

if (i > 0 && nums[i] == nums[i - 1]) continue;

skip duplicate fixed elements to avoid repeated triplets

while (left < right) {

two-pointer loop to find pairs that sum with fixed to zero

int sum = nums[i] + nums[left] + nums[right];

calculate current triplet sum

if (sum == 0) {

found valid triplet, add to result

while (left < right && nums[left] == nums[left + 1]) left++;

skip duplicates on left pointer

while (left < right && nums[right] == nums[right - 1]) right--;

skip duplicates on right pointer

left++; right--;

move pointers inward after recording triplet

else if (sum < 0) { left++; } else { right--; }

adjust pointers to increase or decrease sum

Output

[-1, -1, 2]

[-1, 0, 1]

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers scanning the array

Space: O(k) where k is the number of triplets found, for storing results

vs Alternative: Naive approach is O(n^3) by checking all triplets; two-pointer reduces to O(n^2)

Edge Cases

empty list

returns empty result with no triplets

DSA C++

for (int i = 0; i < n - 2; i++) {

list with less than 3 elements

returns empty result as no triplets possible

DSA C++

for (int i = 0; i < n - 2; i++) {

all zeros

returns one triplet [0, 0, 0] without duplicates

DSA C++

while (left < right && nums[left] == nums[left + 1]) left++;

no triplets sum to zero

returns empty result

DSA C++

while (left < right) { ... }

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique results, use sorting plus two-pointer scanning to efficiently find all combinations.

Common Mistakes

Mistake: Not sorting the array before two-pointer search
Fix: Sort the array first to enable two-pointer technique and duplicate skipping

Mistake: Not skipping duplicates for fixed, left, or right pointers
Fix: Add checks to skip duplicates to avoid repeated triplets

Mistake: Moving pointers incorrectly when sum equals zero
Fix: After recording triplet, move both pointers inward skipping duplicates

Summary

Finds all unique triplets in a list that sum to zero.

Use when you need to find combinations of three numbers summing to zero without repeats.

Sort the list and use two pointers to efficiently find pairs complementing a fixed number.

Practice

1. What is the main goal of the Three Sum Problem All Unique Triplets in an integer array?

easy

A. Find all unique triplets that sum to zero

B. Find the maximum sum of any three numbers

C. Find the triplet with the smallest product

D. Find pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique sets of three numbers in the array whose sum equals zero.

2. Step 2: Clarify uniqueness and sum condition

   Each triplet must be unique (no duplicates) and the sum of the three numbers must be exactly zero.

3. Final Answer:

   Find all unique triplets that sum to zero -> Option A

4. Quick Check:

   Unique triplets with sum zero = Find all unique triplets that sum to zero [OK]

Hint: Look for three numbers adding exactly to zero [OK]

Common Mistakes:

• Confusing pairs with triplets
• Ignoring uniqueness of triplets
• Looking for max or min sums instead of zero sum

2. Which of the following C++ code snippets correctly sorts the input vector nums before applying the two-pointer technique in the Three Sum problem?

easy

A. std::sort(nums);

B. sort(nums, nums + nums.size());

C. nums.sort();

D. std::sort(nums.begin(), nums.end());

Solution

1. Step 1: Identify correct sorting syntax for std::vector

   For a vector, sorting requires iterators: nums.begin() and nums.end().

2. Step 2: Check each option

   std::sort(nums.begin(), nums.end()); uses correct syntax. sort(nums, nums + nums.size()); is invalid because nums is a vector, not a pointer array. nums.sort(); is invalid because vector has no sort() method. std::sort(nums); is invalid because std::sort requires two iterators.

3. Final Answer:

   std::sort(nums.begin(), nums.end()); -> Option D

4. Quick Check:

   Correct vector sorting = std::sort(nums.begin(), nums.end()); [OK]

Hint: Use iterators with std::sort for vectors [OK]

Common Mistakes:

• Using pointer syntax on vectors
• Calling sort() as a vector method
• Passing only one argument to std::sort

3. What is the output of the following C++ code snippet that finds all unique triplets summing to zero?

std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  if (i > 0 && nums[i] == nums[i-1]) continue;
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({nums[i], nums[left], nums[right]});
      while (left < right && nums[left] == nums[left+1]) left++;
      while (left < right && nums[right] == nums[right-1]) right--;
      left++; right--;
    } else if (sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}
for (auto &triplet : result) {
  for (int num : triplet) std::cout << num << ' ';
  std::cout << '\n';
}

medium

A. No output

B. -1 -1 2
-1 0 1

C. -4 -1 2
-1 0 1

D. -1 0 1
0 1 2

Solution

1. Step 1: Sort the array and initialize pointers

   Sorted array: [-4, -1, -1, 0, 1, 2]. Loop through each element with two pointers to find triplets summing to zero.

2. Step 2: Identify unique triplets with sum zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1]. These are printed line by line.

3. Final Answer:

   -1 -1 2 -1 0 1 -> Option B

4. Quick Check:

   Unique triplets = [-1, -1, 2] and [-1, 0, 1] [OK]

Hint: Sort first, then use two pointers to find zero sum triplets [OK]

Common Mistakes:

• Not skipping duplicates
• Incorrect pointer movement
• Printing wrong triplets

4. Identify the bug in the following code snippet for the Three Sum problem:

std::vector<int> nums = {-2, 0, 1, 1, 2};
std::vector result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
  int left = i + 1, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[i] + nums[left] + nums[right];
    if (sum == 0) {
      result.push_back({nums[i], nums[left], nums[right]});
      left++;
      right--;
    } else if (sum < 0) {
      left++;
    } else {
      right--;
    }
  }
}

medium

A. Missing check to skip duplicate i values

B. Incorrect sorting of the input vector

C. Wrong initialization of pointers left and right

D. Using push_back instead of emplace_back

Solution

1. Step 1: Analyze duplicate handling for i

   The code does not skip duplicate values for i, which can cause duplicate triplets in the result.

2. Step 2: Confirm other parts are correct

   Sorting is correct, pointers are initialized properly, and push_back is valid here.

3. Final Answer:

   Missing check to skip duplicate i values -> Option A

4. Quick Check:

   Skipping duplicates for i avoids repeated triplets [OK]

Hint: Always skip duplicate i to avoid repeated triplets [OK]

Common Mistakes:

• Not skipping duplicates for i
• Skipping duplicates only for pointers
• Assuming sorting fixes duplicates automatically

5. Given the input array nums = {0, 0, 0, 0}, what is the correct output of the Three Sum problem that finds all unique triplets summing to zero?

hard

A. []

B. [[0, 0, 0], [0, 0, 0]]

C. [[0, 0, 0]]

D. [[0, 0]]

Solution

1. Step 1: Understand the input with duplicates

   All elements are zero, so the only triplet summing to zero is [0, 0, 0].

2. Step 2: Ensure uniqueness of triplets

   Even though multiple zeros exist, only one unique triplet [0, 0, 0] should be returned.

3. Final Answer:

   [[0, 0, 0]] -> Option C

4. Quick Check:

   Unique triplet with zeros = [[0, 0, 0]] [OK]

Hint: Multiple zeros produce one unique triplet [OK]

Common Mistakes:

• Returning duplicate triplets
• Returning pairs instead of triplets
• Returning empty result for all zeros