Problem Link: Partition Equal Subset Sum
We are given an array ‘ARR’ with N positive integers. We need to find if we can partition the array into two subsets such that the sum of elements of each subset is equal to the other.
If we can partition, return true else return false.
Examples
Example:
Practice:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Memorization Approach
Algorithm / Intuition
This question is a slight modification of the problem discussed in Subset-sum equal to target. We need to partition the array(say S) into two subsets(say S1 and S2). According to the question:
- Sum of elements of S1 + sum of elements of S2 = sum of elements of S.
- Sum of elements of S1 = sum of elements of S2.
These two conditions imply that S1 = S2 = (S/2).
Now,
- If S (sum of elements of the input array) is odd , there is no way we can divide it into two equal halves, so we can simply return false.
- If S is even, then we need to find a subsequence in the input array whose sum is equal to S/2 because if we find one subsequence with sum S/2, the remaining elements sum will be automatically S/2. So, we can partition the given array. Hence we return true.
Note: Readers are highly advised to watch this video “Recursion on Subsequences” to understand how we generate subsequences using recursion.
From here we will try to find a subsequence in the array with target = S/2 as discussed in Subset-sum equal to the target
Steps to form the recursive solution:
We will first form the recursive solution by the three points mentioned in the Dynamic Programming Introduction.
Step 1: Express the problem in terms of indexes.
The array will have an index but there is one more parameter “target”. We are given the initial problem to find whether there exists in the whole array a subsequence whose sum is equal to the target.
So, we can say that initially, we need to find(n-1, target) which means that we need to find whether there exists a subsequence in the array from index 0 to n-1, whose sum is equal to the target. Similarly, we can generalize it for any index ind as follows:
Base Cases:
- If target == 0, it means that we have already found the subsequence from the previous steps, so we can return true.
- If ind==0, it means we are at the first element, so we need to return arr[ind]==target. If the element is equal to the target we return true else false.
Step 2: Try out all possible choices at a given index.
We need to generate all the subsequences. We will use the pick/non-pick technique as discussed in this video “Recursion on Subsequences”.
We have two choices:
- Exclude the current element in the subsequence: We first try to find a subsequence without considering the current index element. For this, we will make a recursive call to f(ind-1,target).
- Include the current element in the subsequence: We will try to find a subsequence by considering the current index as element as part of subsequence. As we have included arr[ind], the updated target which we need to find in the rest if the array will be target – arr[ind]. Therefore, we will call f(ind-1,target-arr[ind]).
Note: We will consider the current element in the subsequence only when the current element is less or equal to the target.
Step 3: Return (taken || notTaken)
As we are looking for only one subset, if any of the one among taken or not taken returns true, we can return true from our function. Therefore, we return ‘or(||)’ of both of them.
The final pseudocode after steps 1, 2, and 3:
Steps to memoize a recursive solution:
If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:
- Create a dp array of size [n][k+1]. The size of the input array is ‘n’, so the index will always lie between ‘0’ and ‘n-1’. The target can take any value between ‘0’ and ‘k’. Therefore we take the dp array as dp[n][k+1]
- We initialize the dp array to -1.
- Whenever we want to find the answer of particular parameters (say f(ind,target)), we first check whether the answer is already calculated using the dp array(i.e dp[ind][target]!= -1 ). If yes, simply return the value from the dp array.
- If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind][target] to the solution we get.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if it's possible to partition the array into two subsets with equal sum
bool subsetSumUtil(int ind, int target, vector<int>& arr, vector<vector<int>>& dp) {
// Base case: If the target sum is 0, we found a valid partition
if (target == 0)
return true;
// Base case: If we have considered all elements and the target is still not 0, return false
if (ind == 0)
return arr[0] == target;
// If the result for this state is already calculated, return it
if (dp[ind][target] != -1)
return dp[ind][target];
// Recursive cases
// 1. Exclude the current element
bool notTaken = subsetSumUtil(ind - 1, target, arr, dp);
// 2. Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp);
// Store the result in the DP table and return
return dp[ind][target] = notTaken || taken;
}
// Function to check if the array can be partitioned into two equal subsets
bool canPartition(int n, vector<int>& arr) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 == 1)
return false;
else {
int k = totSum / 2;
// Create a DP table with dimensions n x k+1 and initialize with -1
vector<vector<int>> dp(n, vector<int>(k + 1, -1));
// Call the subsetSumUtil function to check if it's possible to partition
return subsetSumUtil(n - 1, k, arr, dp);
}
}
int main() {
vector<int> arr = {2, 3, 3, 3, 4, 5};
int n = arr.size();
if (canPartition(n, arr))
cout << "The Array can be partitioned into two equal subsets";
else
cout << "The Array cannot be partitioned into two equal subsets";
return 0;
}
import java.util.*;
class TUF {
// Helper function to check if there exists a subset with a given sum
static boolean subsetSumUtil(int ind, int target, int arr[], int[][] dp) {
// If the target sum is 0, we have found a valid subset
if (target == 0)
return true;
// If we have processed all elements in the array
if (ind == 0)
return arr[0] == target;
// If this subproblem has already been solved, return the result
if (dp[ind][target] != -1)
return dp[ind][target] == 0 ? false : true;
// Try not taking the current element into the subset
boolean notTaken = subsetSumUtil(ind - 1, target, arr, dp);
// Try taking the current element into the subset if it doesn't exceed the target
boolean taken = false;
if (arr[ind] <= target)
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp);
// Memoize the result and return true if either choice results in a valid subset
dp[ind][target] = notTaken || taken ? 1 : 0;
return notTaken || taken;
}
// Main function to check if the array can be partitioned into two equal subsets
static boolean canPartition(int n, int[] arr) {
// Calculate the total sum of the array elements
int totSum = 0;
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into equal subsets
if (totSum % 2 == 1)
return false;
else {
// Calculate the target sum for each subset
int k = totSum / 2;
// Create a memoization table
int dp[][] = new int[n][k + 1];
for (int row[] : dp)
Arrays.fill(row, -1);
// Call the helper function to check if a valid subset exists
return subsetSumUtil(n - 1, k, arr, dp);
}
}
public static void main(String args[]) {
int arr[] = {2, 3, 3, 3, 4, 5};
int n = arr.length;
// Check if the array can be partitioned into two equal subsets
if (canPartition(n, arr))
System.out.println("The Array can be partitioned into two equal subsets");
else
System.out.println("The Array cannot be partitioned into two equal subsets");
}
}
def subsetSumUtil(ind, target, arr, dp):
# Base case: If the target sum is 0, we have found a subset that sums to the target.
if target == 0:
return True
# Base case: If we have reached the first element of the array, check if it equals the target.
if ind == 0:
return arr[0] == target
# Check if the result for this combination of 'ind' and 'target' has already been computed.
if dp[ind][target] != -1:
return dp[ind][target]
# Recursive cases:
# 1. Try not taking the current element.
notTaken = subsetSumUtil(ind - 1, target, arr, dp)
# 2. Try taking the current element if it is less than or equal to the target.
taken = False
if arr[ind] <= target:
taken = subsetSumUtil(ind - 1, target - arr[ind], arr, dp)
# Update the DP table and return the result.
dp[ind][target] = notTaken or taken
return dp[ind][target]
def canPartition(n, arr):
# Calculate the total sum of the array elements.
totSum = sum(arr)
# If the total sum is odd, it cannot be partitioned into two equal subsets.
if totSum % 2 == 1:
return False
else:
# Calculate the target sum for each subset.
k = totSum // 2
# Initialize a memoization table for dynamic programming.
dp = [[-1 for i in range(k + 1)] for j in range(n)]
# Call the subsetSumUtil function to check if a subset with sum 'k' exists.
return subsetSumUtil(n - 1, k, arr, dp)
def main():
arr = [2, 3, 3, 3, 4, 5]
n = len(arr)
# Check if the array can be partitioned into two equal subsets and print the result.
if canPartition(n, arr):
print("The Array can be partitioned into two equal subsets")
else:
print("The Array cannot be partitioned into two equal subsets")
if __name__ == "__main__":
main()
function canPartition(n, arr) {
let totSum = 0;
// Calculate the total sum of elements in the array
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 === 1) return false;
else {
const k = totSum / 2;
// Create a 2D array to store results of subproblems (memoization)
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(k + 1).fill(-1);
}
// Helper function to solve the subset sum problem
function subsetSumUtil(ind, target) {
if (target === 0) return true;
if (ind === 0) return arr[0] === target;
if (dp[ind][target] !== -1) return dp[ind][target];
const notTaken = subsetSumUtil(ind - 1, target);
let taken = false;
if (arr[ind] <= target) {
taken = subsetSumUtil(ind - 1, target - arr[ind]);
}
return (dp[ind][target] = notTaken || taken);
}
// Call the subsetSumUtil function to check if partition is possible
return subsetSumUtil(n - 1, k);
}
}
// Main function
function main() {
const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;
if (canPartition(n, arr)) {
console.log("The Array can be partitioned into two equal subsets");
} else {
console.log("The Array cannot be partitioned into two equal subsets");
}
}
// Run the main function
main();
Output: The array can be partitioned into two equal subsets
Complexity Analysis
Time Complexity: O(N*K) + O(N)
Reason: There are N*K states therefore at max ‘N*K’ new problems will be solved and we are running a for loop for ‘N’ times to calculate the total sum
Space Complexity: O(N*K) + O(N)
Reason: We are using a recursion stack space(O(N)) and a 2D array ( O(N*K)).
Tabulation Approach
Algorithm / Intuition
To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can set its type as bool and initialize it as false.
First, we need to initialize the base conditions of the recursive solution.
- If target == 0, ind can take any value from 0 to n-1, therefore we need to set the value of the first column as true.
- The first-row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only the cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). Please note that it can happen that arr[0]>target, so we first check it: if(arr[0]<=target) then set dp[0][arr[0]] = true.
- After that, we will set our nested for loops to traverse the dp array, and following the logic discussed in the recursive approach, we will set the value of each cell. Instead of recursive calls, we will use the dp array itself.
- At last, we will return dp[n-1][k] as our answer.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if it's possible to partition the array into two subsets with equal sum
bool canPartition(int n, vector<int>& arr) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 == 1)
return false;
else {
int k = totSum / 2;
// Create a DP table with dimensions n x k+1, initialized with false
vector<vector<bool>> dp(n, vector<bool>(k + 1, false));
// Base case: If the target sum is 0, it can be achieved by not selecting any elements
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the first row based on the first element of the array
if (arr[0] <= k)
dp[0][arr[0]] = true;
// Fill in the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 1; target <= k; target++) {
// Exclude the current element
bool notTaken = dp[ind - 1][target];
// Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = dp[ind - 1][target - arr[ind]];
// Update the DP table
dp[ind][target] = notTaken || taken;
}
}
// The final result is in the last cell of the DP table
return dp[n - 1][k];
}
}
int main() {
vector<int> arr = {2, 3, 3, 3, 4, 5};
int n = arr.size();
if (canPartition(n, arr))
cout << "The Array can be partitioned into two equal subsets";
else
cout << "The Array cannot be partitioned into two equal subsets";
return 0;
}
import java.util.*;
class TUF {
// Function to check if it's possible to partition the array into two equal subsets
static boolean canPartition(int n, int[] arr) {
// Calculate the total sum of the array elements
int totSum = 0;
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into equal subsets
if (totSum % 2 == 1)
return false;
else {
// Calculate the target sum for each subset
int k = totSum / 2;
// Create a DP table to store the results of subproblems
boolean dp[][] = new boolean[n][k + 1];
// Initialize the first row of the DP table
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the first column of the DP table
if (arr[0] <= k) {
dp[0][arr[0]] = true;
}
// Fill in the DP table using bottom-up dynamic programming
for (int ind = 1; ind < n; ind++) {
for (int target = 1; target <= k; target++) {
// Calculate if the current element is not taken
boolean notTaken = dp[ind - 1][target];
// Calculate if the current element is taken
boolean taken = false;
if (arr[ind] <= target) {
taken = dp[ind - 1][target - arr[ind]];
}
// Update the DP table for the current element and target sum
dp[ind][target] = notTaken || taken;
}
}
// The result is stored in the last cell of the DP table
return dp[n - 1][k];
}
}
public static void main(String args[]) {
int arr[] = {2, 3, 3, 3, 4, 5};
int n = arr.length;
// Check if the array can be partitioned into two equal subsets
if (canPartition(n, arr))
System.out.println("The Array can be partitioned into two equal subsets");
else
System.out.println("The Array cannot be partitioned into two equal subsets");
}
}
def canPartition(n, arr):
# Calculate the total sum of the array elements.
totSum = sum(arr)
# If the total sum is odd, it cannot be partitioned into two equal subsets.
if totSum % 2 == 1:
return False
else:
# Calculate the target sum for each subset.
k = totSum // 2
# Initialize a dynamic programming table (dp) to store subproblem results.
dp = [[False for j in range(k + 1)] for i in range(n)]
# Initialize the base case: An empty subset can always achieve a sum of 0.
for i in range(n):
dp[i][0] = True
# Initialize the base case for the first element in the array.
if arr[0] <= k:
dp[0][arr[0]] = True
# Fill in the DP table using a bottom-up approach.
for ind in range(1, n):
for target in range(1, k + 1):
# If the current element is not taken, the result is the same as the previous row.
notTaken = dp[ind - 1][target]
# If the current element is taken, subtract its value from the target and check the previous row.
taken = False
if arr[ind] <= target:
taken = dp[ind - 1][target - arr[ind]]
# Update the DP table with the result of taking or not taking the current element.
dp[ind][target] = notTaken or taken
# The final result is stored in the bottom-right cell of the DP table.
return dp[n - 1][k]
def main():
arr = [2, 3, 3, 3, 4, 5]
n = len(arr)
# Check if the array can be partitioned into two equal subsets and print the result.
if canPartition(n, arr):
print("The Array can be partitioned into two equal subsets")
else:
print("The Array cannot be partitioned into two equal subsets")
if __name__ == '__main__':
main()
function canPartition(n, arr) {
let totSum = 0;
// Calculate the total sum of elements in the array
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 === 1) return false;
else {
const k = totSum / 2;
// Create a 2D boolean array to store results of subproblems (dynamic programming)
const dp = new Array(n);
for (let i = 0; i < n; i++) {
dp[i] = new Array(k + 1).fill(false);
}
// Initialize the first row of the dp array
for (let i = 0; i < n; i++) {
dp[i][0] = true;
}
// Initialize the first column of the dp array
if (arr[0] <= k) {
dp[0][arr[0]] = true;
}
// Fill the dp array using bottom-up dynamic programming
for (let ind = 1; ind < n; ind++) {
for (let target = 1; target <= k; target++) {
const notTaken = dp[ind - 1][target];
let taken = false;
if (arr[ind] <= target) {
taken = dp[ind - 1][target - arr[ind]];
}
dp[ind][target] = notTaken || taken;
}
}
// The final cell dp[n-1][k] contains the result
return dp[n - 1][k];
}
}
// Main function
function main() {
const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;
if (canPartition(n, arr)) {
console.log("The Array can be partitioned into two equal subsets");
} else {
console.log("The Array cannot be partitioned into two equal subsets");
}
}
// Run the main function
main();
Output: The array can be partitioned into two equal subsets
Complexity Analysis
Time Complexity: O(N*K) +O(N)
Reason: There are two nested loops that account for O(N*K) and at starting we are running a for loop to calculate totSum.
Space Complexity: O(N*K)
Reason: We are using an external array of size ‘N*K’. Stack Space is eliminated.
Space Optimization Approach
Algorithm / Intuition
If we closely look the relation,
dp[ind][target] = dp[ind-1][target] || dp[ind-1][target-arr[ind]]
We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.
Note: Whenever we create a new row ( say cur), we need to explicitly set its first element is true according to our base condition.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if it's possible to partition the array into two subsets with equal sum
bool canPartition(int n, vector<int>& arr) {
int totSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 == 1)
return false;
else {
int k = totSum / 2;
// Create a vector to represent the previous row of the DP table
vector<bool> prev(k + 1, false);
// Base case: If the target sum is 0, it can be achieved by not selecting any elements
prev[0] = true;
// Initialize the first row based on the first element of the array
if (arr[0] <= k)
prev[arr[0]] = true;
// Fill in the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
// Create a vector to represent the current row of the DP table
vector<bool> cur(k + 1, false);
cur[0] = true;
for (int target = 1; target <= k; target++) {
// Exclude the current element
bool notTaken = prev[target];
// Include the current element if it doesn't exceed the target
bool taken = false;
if (arr[ind] <= target)
taken = prev[target - arr[ind]];
// Update the current row of the DP table
cur[target] = notTaken || taken;
}
// Set the current row as the previous row for the next iteration
prev = cur;
}
// The final result is in the last cell of the previous row of the DP table
return prev[k];
}
}
int main() {
vector<int> arr = {2, 3, 3, 3, 4, 5};
int n = arr.size();
if (canPartition(n, arr))
cout << "The Array can be partitioned into two equal subsets";
else
cout << "The Array cannot be partitioned into two equal subsets";
return 0;
}
import java.util.*;
class TUF {
// Function to check if it's possible to partition the array into two equal subsets
static boolean canPartition(int n, int[] arr) {
// Calculate the total sum of the array elements
int totSum = 0;
for (int i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into equal subsets
if (totSum % 2 == 1)
return false;
else {
// Calculate the target sum for each subset
int k = totSum / 2;
// Create two arrays to store the DP results for the previous and current rows
boolean prev[] = new boolean[k + 1];
// Initialize the first row of the DP table
prev[0] = true;
// Initialize the first column of the DP table
if (arr[0] <= k) {
prev[arr[0]] = true;
}
// Fill in the DP table using bottom-up dynamic programming
for (int ind = 1; ind < n; ind++) {
boolean cur[] = new boolean[k + 1];
cur[0] = true;
for (int target = 1; target <= k; target++) {
// Calculate if the current element is not taken
boolean notTaken = prev[target];
// Calculate if the current element is taken
boolean taken = false;
if (arr[ind] <= target) {
taken = prev[target - arr[ind]];
}
// Update the DP table for the current element and target sum
cur[target] = notTaken || taken;
}
// Update the previous row with the current row for the next iteration
prev = cur;
}
// The result is stored in the last cell of the DP table
return prev[k];
}
}
public static void main(String args[]) {
int arr[] = {2, 3, 3, 3, 4, 5};
int n = arr.length;
// Check if the array can be partitioned into two equal subsets
if (canPartition(n, arr))
System.out.println("The Array can be partitioned into two equal subsets");
else
System.out.println("The Array cannot be partitioned into two equal subsets");
}
}
def canPartition(n, arr):
# Calculate the total sum of the array elements.
totSum = sum(arr)
# If the total sum is odd, it cannot be partitioned into two equal subsets.
if totSum % 2 == 1:
return False
else:
# Calculate the target sum for each subset.
k = totSum // 2
# Initialize a boolean array 'prev' to store the results for the previous row.
prev = [False] * (k + 1)
prev[0] = True # Base case: An empty subset can always achieve a sum of 0.
# Handle the base case for the first element in the array.
if arr[0] <= k:
prev[arr[0]] = True
# Iterate through the elements in the array.
for ind in range(1, n):
# Initialize a new boolean array 'cur' for the current row.
cur = [False] * (k + 1)
cur[0] = True # An empty subset can always achieve a sum of 0.
# Fill in the 'cur' array using dynamic programming.
for target in range(1, k + 1):
# If the current element is not taken, the result is the same as the previous row.
notTaken = prev[target]
# If the current element is taken, subtract its value from the target and check the previous row.
taken = False
if arr[ind] <= target:
taken = prev[target - arr[ind]]
# Update the 'cur' array with the result of taking or not taking the current element.
cur[target] = notTaken or taken
# Update 'prev' to 'cur' for the next iteration.
prev = cur
# The final result is stored in 'prev[k]', indicating whether a subset with sum 'k' is possible.
return prev[k]
def main():
arr = [2, 3, 3, 3, 4, 5]
n = len(arr)
# Check if the array can be partitioned into two equal subsets and print the result.
if canPartition(n, arr):
print("The Array can be partitioned into two equal subsets")
else:
print("The Array cannot be partitioned into two equal subsets")
if __name__ == "__main__":
main()
function canPartition(n, arr) {
let totSum = 0;
// Calculate the total sum of elements in the array
for (let i = 0; i < n; i++) {
totSum += arr[i];
}
// If the total sum is odd, it cannot be partitioned into two equal subsets
if (totSum % 2 === 1) return false;
else {
const k = totSum / 2;
// Initialize the previous row (array) for dynamic programming
const prev = new Array(k + 1).fill(false);
prev[0] = true;
// Initialize the first column of the dp array
if (arr[0] <= k) {
prev[arr[0]] = true;
}
// Fill the dp array using bottom-up dynamic programming
for (let ind = 1; ind < n; ind++) {
const cur = new Array(k + 1).fill(false);
cur[0] = true;
for (let target = 1; target <= k; target++) {
const notTaken = prev[target];
let taken = false;
if (arr[ind] <= target) {
taken = prev[target - arr[ind]];
}
cur[target] = notTaken || taken;
}
// Update the previous row (array) for the next iteration
prev = cur;
}
// The final element of the 'prev' array (prev[k]) contains the result
return prev[k];
}
}
// Main function
function main() {
const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;
if (canPartition(n, arr)) {
console.log("The Array can be partitioned into two equal subsets");
} else {
console.log("The Array cannot be partitioned into two equal subsets");
}
}
// Run the main function
main();
Output:The Array can be partitioned into two equal subsets
Complexity Analysis
Time Complexity: O(N*K) +O(N)
Reason: There are two nested loops that account for O(N*K) and at starting we are running a for loop to calculate totSum.
Space Complexity: O(K)
Reason: We are using an external array of size ‘K+1’ to store only one row.
Video Explanation
Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article