Find all triplets in an array that add up to a given sum - Brute Force Technique

Hello everyone, Welcome to Sprint Master! 

In this post, we are going to look at solving the following coding question 

"Find all triplets in an array that add up to a given sum" 

As you all know, a problem can be solved in multiple ways, and this particular question can be solved in 4 different ways. In today's post we will be looking at one of the ways to solve this question by using Brute-Force technique. 

In this approach, we will try to find all the triplets that are possible from the given array, and for each triplet we calculate the sum and check if that sum matches with the given sum. If the sum matches, then we have a triplet.

I have a more elaborate discussion of this approach in the following video.

 

You can also find the complete code snippet with which we can solve this problem down below. 

import java.util.Arrays;

public class Solution1{

     public static void main(String []args){

        System.out.println("Finding triplets with Brute-force technique");

        int[] arr = {1,5,9,2,8,4};

        Solution1 solution = new Solution1();

        solution.findTriplet(arr, 15);

     }

     

     public void findTriplet(int[] arr, int sum) {

        int n = arr.length;

        if(n<3) {

            System.out.println("No pairs found");

        }

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

            for(int j=i+1;j<n-1;j++) {

                for(int k=j+1;k<n;k++) {

                    if(arr[i]+arr[j]+arr[k] == sum) {

                        System.out.println("Triplet found: ["+arr[i]+","+arr[j]+","+arr[k]+"]");

                    }

                }

            }

        }

    }

}

The time complexity of this approach is O(n^3). 

This is because, to find each element of the triplet, we are iterating over the array. To be more clear, we first select an element by iterating over the array, and for each selected first element, we iterate over the rest of the array to find the second element, and for each second element, we find the third element in a similar way.

When you combine all of that, the time complexity turns out to be (n-2)x(n-2)x(n-2) which is O(n^3) since we care only about the dominant term.

We can further reduce this time complexity, and in the next post, we will see how to reduce it.

Source : https://sprintmaster.blogspot.com/2020/12/find-all-triplets-in-array-that-add-up.html

YouTube Link : Sprint Master - YouTube