Problem Statement:
Given an array a of n integers find all possible Pythagorean triplets from the array.

What is Pythagorean triplet?

A Pythagorean triple consists of three positive integers a, b, and c, such that a² + b² = c². this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a² + b² = c²“.

Pythagorean Triplet

Solution:
[Read more…]

Problem Statement:
Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

Solution:
Brute force approach is of O(n^4) but we can solve it in O(n^2) by using the approach in Non duplicate pairs that sum to S.

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in Non duplicate pairs that sum to S, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).