Three Sum Problem All Unique Triplets in DSA C++ - Build from Scratch

Three Sum Problem All Unique Triplets

📖 Scenario: You are working on a financial app that analyzes daily stock price changes. You want to find all unique sets of three days where the total price change sums to zero. This helps identify balanced periods where gains and losses cancel out.

🎯 Goal: Build a program that finds all unique triplets in an integer array whose sum is zero. The output should list each triplet once, sorted in ascending order within the triplet.

📋 What You'll Learn

Create a vector of integers named nums with the exact values: {-1, 0, 1, 2, -1, -4}.

Create an integer variable n to store the size of nums.

Implement the three sum logic using sorting and two pointers to find all unique triplets that sum to zero.

Store the results in a vector of vectors named result.

Print each triplet in result on its own line in the format: [a, b, c].

💡 Why This Matters

🌍 Real World

Finding balanced triplets in financial data helps identify periods where gains and losses offset each other, useful for risk analysis.

💼 Career

This problem is common in coding interviews and helps develop skills in sorting, two-pointer technique, and handling duplicates.

1

Create the input vector

Create a vector of integers called nums with these exact values: {-1, 0, 1, 2, -1, -4}.

DSA C++

#include 
#include 

int main() {
    // Create vector nums with values {-1, 0, 1, 2, -1, -4}
    // Your code here
}

Hint

Use std::vector<int> and initialize it with the given values inside curly braces.

2

Add size variable

Create an integer variable called n and set it to the size of nums using nums.size().

DSA C++

#include 
#include 

int main() {
    std::vector nums = {-1, 0, 1, 2, -1, -4};
    // Create int n and set it to nums.size()
    // Your code here
}

Hint

Use int n = nums.size(); to get the number of elements in the vector.

3

Implement three sum logic

Sort the vector nums. Create a vector of vectors of integers called result. Use a for loop with variable i from 0 to n - 3. Inside the loop, use two pointers left and right to find all unique triplets that sum to zero and add them to result.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {-1, 0, 1, 2, -1, -4};
    int n = nums.size();
    // Sort nums
    // Create vector> result
    // Use for loop with i from 0 to n-3
    // Use two pointers left and right to find triplets
    // Add unique triplets to result
    // Your code here
}

Hint

Sort the vector first. Use a for loop for the first element. Use two pointers to find pairs that sum with nums[i] to zero. Skip duplicates to avoid repeated triplets.

4

Print all unique triplets

Use a for loop with variable triplet to iterate over result. Inside the loop, print each triplet in the format [a, b, c] where a, b, and c are the three integers in the triplet.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {-1, 0, 1, 2, -1, -4};
    int n = nums.size();
    std::sort(nums.begin(), nums.end());
    std::vector> result;

    for (int i = 0; i  0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1;
        int 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]});
                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;
            }
        }
    }
    // Print each triplet in result in format [a, b, c]
    // Your code here
}

Hint

Use a range-based for loop to go through each triplet in result. Print the three numbers inside square brackets separated by commas.

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