Table of contents

Find all unique pairs with given sum in the array

Given an array of integers and a target sum, find all unique pairs of elements in the array whose sum equals the target sum. Each pair should only be listed once, and the elements within each pair should be listed in ascending order.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [1, 2, 3, 4, 5]
target = 6
Output: [(1, 5), (2, 4)]
Explanation: The pairs (1, 5) and (2, 4) sum up to 6.

Example 2:
Input:
arr = [2, 4, 3, 3, 5, -1]
target = 7
Output: [(2, 5), (4, 3)]
Explanation: The pairs (2, 5) and (4, 3) sum up to 7. Note that (3, 4) and (4, 3) are considered the same pair.

Example 3:
Input:
arr = [1, 1, 1, 1]
target = 2
Output: [(1, 1)]
Explanation: The only unique pair that sums up to 2 is (1, 1).

Approach to Find All Pairs with a Given Sum

  1. Use a Hash Set to Track Seen Elements:
    • Iterate through the array, and for each element, calculate the needed value (target - element) to reach the target sum.
  2. Check for Pairs:
    • If the needed value is already in the set, add the pair in ascending order to the result list.
    • If not, add the current element to the set, indicating it has been seen.
  3. Return Unique Pairs:
    • To avoid duplicates, always add pairs in ascending order and store pairs only once when encountered.

C++ Program to Find All Pairs with a Given Sum

cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// Function to find all pairs with a given sum
vector<pair<int, int>> findPairsWithSum(const vector<int>& arr, int target) {
    unordered_set<int> seen;
    vector<pair<int, int>> result;

    for (int num : arr) {
        int complement = target - num;
        if (seen.find(complement) != seen.end()) {
            // Add the pair in sorted order
            result.push_back({min(num, complement), max(num, complement)});
        }
        seen.insert(num);
    }

    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int target = 6;
    vector<pair<int, int>> pairs = findPairsWithSum(arr, target);

    cout << "Pairs with sum " << target << ": ";
    for (const auto& p : pairs) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;

    return 0;
}

Java Program to Find All Pairs with a Given Sum

java
import java.util.*;

public class FindPairsWithSum {

    // Function to find all pairs with a given sum
    public static List<int[]> findPairsWithSum(int[] arr, int target) {
        Set<Integer> seen = new HashSet<>();
        List<int[]> result = new ArrayList<>();

        for (int num : arr) {
            int complement = target - num;
            if (seen.contains(complement)) {
                // Add the pair in sorted order
                result.add(new int[]{Math.min(num, complement), Math.max(num, complement)});
            }
            seen.add(num);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 6;
        List<int[]> pairs = findPairsWithSum(arr, target);

        System.out.print("Pairs with sum " + target + ": ");
        for (int[] pair : pairs) {
            System.out.print("(" + pair[0] + ", " + pair[1] + ") ");
        }
        System.out.println();
    }
}

Python Program to Find All Pairs with a Given Sum

python
# Function to find all pairs with a given sum
def find_pairs_with_sum(arr, target):
    seen = set()
    result = []

    for num in arr:
        complement = target - num
        if complement in seen:
            # Add the pair in sorted order
            result.append((min(num, complement), max(num, complement)))
        seen.add(num)

    return result

# Example usage
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    target = 6
    pairs = find_pairs_with_sum(arr, target)
    print("Pairs with sum", target, ":", pairs)
  • Time Complexity: O(n) since each element is processed once, and set operations (insert and lookup) are on average O(1).
  • Space Complexity: O(n) due to the hash set used to store seen elements.

DSA

Related Articles