SkylineWebZ

Table of Content [Naive Approach] Consider substrings starting from every index – O(n ^ 2) Time and O(1) Space Starting from every index and maximum of all such lengths will be our response; we mostly locate length of longest substring with unique characters. We build a new visited array of size 256 (We can also use a hash set, but a visited array would be better because we know that the character set is 256 in most of the cases) to keep track of included characters in the substring in order to ascertain the length of the longest substring with distinct characters starting from an index. C++ C Java Python JavaScript Output 7

A more effective answer to the 2Sum challenge comes from hashing. We loop traverse the items of the array storing each integer in an unordered set instead of verifying every conceivable pair. We find the complement of every number—that is, target less current number—then see whether this complement exists in the set. Should it so, we have located the pair that adds up to the target. This method greatly lowers the time complexity and enables linear time O(n) solution of the problem. Methodically approach: C++ Java Python Js Output 1 Time Complexity: O(n), for single iteration over the arrayAuxiliary Space: O(n), for hashmap

One intends to apply the two-pointer strategy. But the array has to be sorted if one is utilizing the two- pointer approach. Once the array is sorted, we can apply this method retaining one pointer at the beginning (left) and another at the end (right) of the array. Check the sum of the components at these two pointers next as well: C++ C Java Python Output 1 Time Complexity: O(n*log(n)), for sorting the arrayAuxiliary Space: O(1)

Binary search lets us also tackle this issue. Searching element in sorted array will take O(log(n)) time as we know it. First we arrange the array. After that, for every number arr[i] in the array, we first find its complement—that is, target less current number—then apply binary search to rapidly explore the subarray following index i for this complement. We return false if we never discover a complement (after looking over all the numbers); we return true if we do find the complement. C++ C Java Python JS Output 1 Time Complexity: O(n*log(n)), for sorting the arrayAuxiliary Space: O(1)

The aim is to determine whether there is a pair of items in an array whose sum equals the target value given an array arr[] of n integers. The 2Sum problem is a variant of this one. Table of Content [Naive Approach] Generating all Possible Pairs – O(n^2) time and O(1) space The very basic approach is to generate all the possible pairs and check if any of them add up to the target value. To generate all pairs, we simply run two nested loops. C++ C Java Python Output 1 Time Complexity: O(n²), for using two nested loopsAuxiliary Space: O(1)

Problem Statement – Jump Game II You are given an array of non-negative integers nums where each element in the array represents your maximum jump length from that position. Your goal is to reach the last index starting from the first index using the minimum number of jumps. You can assume that you can always reach the last index. Example: Input: nums = [2, 3, 1, 1, 4] Output: 2 Explanation: Jump from index 0 to 1 (nums[0] = 2), then jump from index 1 to 4 (nums[1] = 3). Approach: We are asked to minimize the number of jumps. The optimal approach for this problem is Dynamic Programming (DP) where we keep track of the minimum jumps required to reach each index in the array. Dynamic Programming Explanation: Time Complexity: Optimized Approach: An optimized greedy approach with O(n) time complexity is also possible, where we dynamically track the farthest index we can reach within the current jump range and increment the number of jumps accordingly. Code in Various Languages: 1. C: #include <stdio.h>#include <limits.h>int jump(int* nums, int numsSize) { if (numsSize <= 1) return 0; int dp[numsSize]; for (int i = 0; i < numsSize; i++) dp[i] = INT_MAX; dp[0] = 0; for (int i = 0; i < numsSize; i++) { for (int j = i + 1; j <= i + nums[i] && j < numsSize; j++) { if (dp[j] > dp[i] + 1) { dp[j] = dp[i] + 1; } } } return dp[numsSize – 1];}int main() { int nums[] = {2, 3, 1, 1, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“%d\n”, jump(nums, size)); // Output: 2 return 0;} 2. C++: #include <iostream>#include <vector>#include <climits>using namespace std;int jump(vector<int>& nums) { int n = nums.size(); if (n <= 1) return 0; vector<int> dp(n, INT_MAX); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = min(dp[j], dp[i] + 1); } } return dp[n – 1];}int main() { vector<int> nums = {2, 3, 1, 1, 4}; cout << jump(nums) << endl; // Output: 2 return 0;} 3. Java: public class JumpGameII { public int jump(int[] nums) { int n = nums.length; if (n <= 1) return 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = Integer.MAX_VALUE; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.min(dp[j], dp[i] + 1); } } return dp[n – 1]; } public static void main(String[] args) { JumpGameII solution = new JumpGameII(); int[] nums = {2, 3, 1, 1, 4}; System.out.println(solution.jump(nums)); // Output: 2 }} 4. Python: def jump(nums): n = len(nums) if n <= 1: return 0 dp = [float(‘inf’)] * n dp[0] = 0 for i in range(n): for j in range(i + 1, min(i + nums[i] + 1, n)): dp[j] = min(dp[j], dp[i] + 1) return dp[n – 1]# Test the functionnums = [2, 3, 1, 1, 4]print(jump(nums)) # Output: 2 5. C#: using System;public class JumpGameII { public int Jump(int[] nums) { int n = nums.Length; if (n <= 1) return 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) dp[i] = int.MaxValue; dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.Min(dp[j], dp[i] + 1); } } return dp[n – 1]; } public static void Main(string[] args) { JumpGameII solution = new JumpGameII(); int[] nums = {2, 3, 1, 1, 4}; Console.WriteLine(solution.Jump(nums)); // Output: 2 }} 6. JavaScript: var jump = function(nums) { let n = nums.length; if (n <= 1) return 0; let dp = new Array(n).fill(Infinity); dp[0] = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.min(dp[j], dp[i] + 1); } } return dp[n – 1];};// Test the functionconst nums = [2, 3, 1, 1, 4];console.log(jump(nums)); // Output: 2 Optimized Approach (Greedy Algorithm) In this approach, instead of using a DP table, we can dynamically track the farthest we can reach in the current jump range, and count how many jumps we need to reach the end. Optimized Approach – Greedy: This approach runs in O(n) time, as we only pass through the array once.

Wildcard Matching Problem In the Wildcard Matching problem, you are given two strings: a text string s and a pattern string p. The pattern string contains two special characters: The goal is to determine if the pattern p matches the entire string s. Problem Statement: Given a string s and a pattern p, return true if p matches s, and false otherwise. Examples: Example 1: Input: s = “aa”, p = “a*”Output: trueExplanation: The pattern “a*” matches the entire string “aa”. Example 2: Input: s = “cb”, p = “?a”Output: falseExplanation: The pattern “?a” does not match the string “cb”. Example 3: Input: s = “adceb”, p = “*a*b”Output: trueExplanation: The pattern “*a*b” matches the string “adceb”. Example 4: Input: s = “acdcb”, p = “a*c?b”Output: falseExplanation: The pattern “a*c?b” does not match the string “acdcb”. Approach: We can solve this problem using Dynamic Programming (DP). Key Observations: Dynamic Programming Approach: We can create a DP table dp[i][j] where: The value dp[i][j] will be true if the substring s[0…i-1] matches the pattern p[0…j-1]. Base Cases: Recurrence Relation: Time and Space Complexity: Code Implementations: 1. C: #include <stdio.h>#include <string.h>#include <stdbool.h>bool isMatch(char *s, char *p) { int m = strlen(s); int n = strlen(p); bool dp[m+1][n+1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; // Both empty string and pattern match // Initialize the first row for patterns starting with ‘*’ for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i][j] = dp[i-1][j-1]; // Exact match or ‘?’ } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; // ‘*’ matches one or more characters } } } return dp[m][n];}int main() { char s[] = “adceb”; char p[] = “*a*b”; printf(“%d\n”, isMatch(s, p)); // Output: 1 (true) return 0;} 2. C++: #include <iostream>#include <vector>using namespace std;bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n];}int main() { string s = “adceb”, p = “*a*b”; cout << isMatch(s, p) << endl; // Output: 1 (true) return 0;} 3. Java: public class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p.charAt(j-1) == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p.charAt(j-1) == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n]; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isMatch(“adceb”, “*a*b”)); // Output: true }} 4. Python: def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j-1] == ‘*’: dp[0][j] = dp[0][j-1] for i in range(1, m + 1): for j in range(1, n + 1): if p[j-1] == s[i-1] or p[j-1] == ‘?’: dp[i][j] = dp[i-1][j-1] elif p[j-1] == ‘*’: dp[i][j] = dp[i-1][j] or dp[i][j-1] return dp[m][n]# Example usage:print(isMatch(“adceb”, “*a*b”)) # Output: True 5. C#: public class Solution { public bool IsMatch(string s, string p) { int m = s.Length, n = p.Length; bool[,] dp = new bool[m + 1, n + 1]; dp[0, 0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0, j] = dp[0, j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i, j] = dp[i-1, j-1]; } else if (p[j-1] == ‘*’) { dp[i, j] = dp[i-1, j] || dp[i, j-1]; } } } return dp[m, n]; } public static void Main(string[] args) { Solution solution = new Solution(); Console.WriteLine(solution.IsMatch(“adceb”, “*a*b”)); // Output: True }} 6. JavaScript: var isMatch = function(s, p) { const m = s.length, n = p.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false)); dp[0][0] = true; for (let j = 1; j <= n; j++) { if (p[j-1] === ‘*’) { dp[0][j] = dp[0][j-1]; } } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (p[j-1] === s[i-1] || p[j-1] === ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] === ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n];};// Example usageconsole.log(isMatch(“adceb”, “*a*b”)); // Output: true Summary:

The Trapping Rain Water problem asks us to compute how much water can be trapped between bars of varying heights after it rains. The problem typically provides an array where each element represents the height of a bar, and we need to calculate how much water can be stored between these bars. Problem Statement: Given an array height[] representing the height of bars in a histogram, the task is to compute the amount of water that can be trapped between the bars after raining. Example: Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6Explanation: The total water trapped is 6 units. Example 2: Input: height = [4,2,0,3,2,5]Output: 9 Approach: To solve this problem efficiently, we can use the two-pointer technique combined with precomputed maximum heights. Here’s a breakdown of the approach: Time Complexity: Code Implementations: 1. C: #include <stdio.h>int trap(int* height, int heightSize) { if (heightSize == 0) return 0; int left = 0, right = heightSize – 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max – height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max – height[right]; } right–; } } return water_trapped;}int main() { int height[] = {0,1,0,2,1,0,1,3,2,1,2,1}; int size = sizeof(height) / sizeof(height[0]); printf(“Trapped Water: %d\n”, trap(height, size)); return 0;} 2. C++: #include <iostream>#include <vector>using namespace std;int trap(vector<int>& height) { int n = height.size(); if (n == 0) return 0; int left = 0, right = n – 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max – height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max – height[right]; } right–; } } return water_trapped;}int main() { vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1}; cout << “Trapped Water: ” << trap(height) << endl; return 0;} 3. Java: public class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) return 0; int left = 0, right = n – 1; int leftMax = 0, rightMax = 0; int waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped; } public static void main(String[] args) { Solution solution = new Solution(); int[] height = {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(“Trapped Water: ” + solution.trap(height)); }} 4. Python: def trap(height): if not height: return 0 left, right = 0, len(height) – 1 left_max, right_max = 0, 0 water_trapped = 0 while left <= right: if height[left] <= height[right]: if height[left] >= left_max: left_max = height[left] else: water_trapped += left_max – height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water_trapped += right_max – height[right] right -= 1 return water_trapped# Example usageheight = [0,1,0,2,1,0,1,3,2,1,2,1]print(f”Trapped Water: {trap(height)}”) 5. C#: using System;public class Solution { public int Trap(int[] height) { int n = height.Length; if (n == 0) return 0; int left = 0, right = n – 1; int leftMax = 0, rightMax = 0; int waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped; } public static void Main(string[] args) { Solution solution = new Solution(); int[] height = {0,1,0,2,1,0,1,3,2,1,2,1}; Console.WriteLine(“Trapped Water: ” + solution.Trap(height)); }} 6. JavaScript: var trap = function(height) { let n = height.length; if (n === 0) return 0; let left = 0, right = n – 1; let leftMax = 0, rightMax = 0; let waterTrapped = 0; while (left <= right) { if (height[left] <= height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { waterTrapped += leftMax – height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { waterTrapped += rightMax – height[right]; } right–; } } return waterTrapped;};// Example usageconst height = [0,1,0,2,1,0,1,3,2,1,2,1];console.log(“Trapped Water: “, trap(height)); Summary:

Problem Statement: Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring. A valid parentheses string is: Example: Example 1: Example 2: Example 3: Approach (Using Dynamic Programming): Time Complexity: Code in Different Languages: 1. C #include <stdio.h>#include <string.h>int longestValidParentheses(char* s) { int n = strlen(s); int dp[n]; memset(dp, 0, sizeof(dp)); int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = (dp[i] > maxLength) ? dp[i] : maxLength; } } return maxLength;}int main() { char s[] = “)()())”; printf(“Longest Valid Parentheses Length: %d\n”, longestValidParentheses(s)); return 0;} 2. C++ #include <iostream>#include <vector>#include <string>using namespace std;int longestValidParentheses(string s) { int n = s.size(); vector<int> dp(n, 0); int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = max(maxLength, dp[i]); } } return maxLength;}int main() { string s = “)()())”; cout << “Longest Valid Parentheses Length: ” << longestValidParentheses(s) << endl; return 0;} 3. Java public class LongestValidParentheses { public static int longestValidParentheses(String s) { int n = s.length(); int[] dp = new int[n]; int maxLength = 0; for (int i = 1; i < n; i++) { if (s.charAt(i) == ‘)’) { if (s.charAt(i – 1) == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s.charAt(i – dp[i – 1] – 1) == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.max(maxLength, dp[i]); } } return maxLength; } public static void main(String[] args) { String s = “)()())”; System.out.println(“Longest Valid Parentheses Length: ” + longestValidParentheses(s)); }} 4. Python def longestValidParentheses(s: str) -> int: n = len(s) dp = [0] * n max_length = 0 for i in range(1, n): if s[i] == ‘)’: if s[i – 1] == ‘(‘: dp[i] = dp[i – 2] + 2 if i – 2 >= 0 else 2 elif i – dp[i – 1] – 1 >= 0 and s[i – dp[i – 1] – 1] == ‘(‘: dp[i] = dp[i – 1] + 2 + (dp[i – dp[i – 1] – 2] if i – dp[i – 1] – 2 >= 0 else 0) max_length = max(max_length, dp[i]) return max_length# Example usages = “)()())”print(f”Longest Valid Parentheses Length: {longestValidParentheses(s)}”) 5. C# using System;public class Solution { public int LongestValidParentheses(string s) { int n = s.Length; int[] dp = new int[n]; int maxLength = 0; for (int i = 1; i < n; i++) { if (s[i] == ‘)’) { if (s[i – 1] == ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] == ‘(‘) { dp[i] = dp[i – 1] + 2 + ((i – dp[i – 1] – 2 >= 0) ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.Max(maxLength, dp[i]); } } return maxLength; } public static void Main(string[] args) { Solution solution = new Solution(); string s = “)()())”; Console.WriteLine($”Longest Valid Parentheses Length: {solution.LongestValidParentheses(s)}”); }} 6. JavaScript var longestValidParentheses = function(s) { const n = s.length; const dp = Array(n).fill(0); let maxLength = 0; for (let i = 1; i < n; i++) { if (s[i] === ‘)’) { if (s[i – 1] === ‘(‘) { dp[i] = (i – 2 >= 0) ? dp[i – 2] + 2 : 2; } else if (i – dp[i – 1] – 1 >= 0 && s[i – dp[i – 1] – 1] === ‘(‘) { dp[i] = dp[i – 1] + 2 + (i – dp[i – 1] – 2 >= 0 ? dp[i – dp[i – 1] – 2] : 0); } maxLength = Math.max(maxLength, dp[i]); } } return maxLength;};// Example usageconst s = “)()())”;console.log(“Longest Valid Parentheses Length:”, longestValidParentheses(s)); Summary:

The problem of Generating Parentheses is to find all combinations of well-formed parentheses given n pairs of parentheses. A well-formed parentheses sequence is a string consisting of n pairs of parentheses where each opening parenthesis ( is closed by a corresponding closing parenthesis ). Problem Statement: Given n, generate all combinations of well-formed parentheses that can be made using n pairs of parentheses. Example: Input: Output: [ “((()))”, “(()())”, “(())()”, “()()()”, “()(()))”] Explanation: For n = 3, there are 5 possible combinations of valid parentheses. Approach: To generate all valid parentheses combinations, we can use Backtracking. The idea is to keep track of the number of opening ( and closing ) parentheses used so far. We can add an opening parenthesis if we have not yet used n opening parentheses, and we can add a closing parenthesis if the number of closing parentheses used is less than the number of opening parentheses used. Time Complexity: Algorithm: Code Implementation in Different Languages: 1. C #include <stdio.h>#include <string.h>void generateParentheses(int n, int open, int close, char *current, char **result, int *resultIndex) { if (open == n && close == n) { result[*resultIndex] = strdup(current); (*resultIndex)++; return; } if (open < n) { current[strlen(current)] = ‘(‘; generateParentheses(n, open + 1, close, current, result, resultIndex); current[strlen(current) – 1] = ‘\0’; } if (close < open) { current[strlen(current)] = ‘)’; generateParentheses(n, open, close + 1, current, result, resultIndex); current[strlen(current) – 1] = ‘\0’; }}char** generateParenthesis(int n, int *returnSize) { char **result = (char **)malloc(sizeof(char*) * 1000); *returnSize = 0; char current[2 * n + 1]; current[0] = ‘\0’; generateParentheses(n, 0, 0, current, result, returnSize); return result;}int main() { int n = 3; int returnSize = 0; char **result = generateParenthesis(n, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); } return 0;} 2. C++ #include <iostream>#include <vector>#include <string>using namespace std;void generateParentheses(int n, int open, int close, string &current, vector<string> &result) { if (open == n && close == n) { result.push_back(current); return; } if (open < n) { current.push_back(‘(‘); generateParentheses(n, open + 1, close, current, result); current.pop_back(); } if (close < open) { current.push_back(‘)’); generateParentheses(n, open, close + 1, current, result); current.pop_back(); }}vector<string> generateParenthesis(int n) { vector<string> result; string current; generateParentheses(n, 0, 0, current, result); return result;}int main() { int n = 3; vector<string> result = generateParenthesis(n); for (const string &str : result) { cout << str << endl; } return 0;} 3. Java import java.util.ArrayList;import java.util.List;public class Solution { public void generateParentheses(int n, int open, int close, String current, List<String> result) { if (open == n && close == n) { result.add(current); return; } if (open < n) { generateParentheses(n, open + 1, close, current + “(“, result); } if (close < open) { generateParentheses(n, open, close + 1, current + “)”, result); } } public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); generateParentheses(n, 0, 0, “”, result); return result; } public static void main(String[] args) { Solution solution = new Solution(); List<String> result = solution.generateParenthesis(3); for (String s : result) { System.out.println(s); } }} 4. Python def generateParentheses(n: int): result = [] def backtrack(current, open, close): if open == n and close == n: result.append(current) return if open < n: backtrack(current + ‘(‘, open + 1, close) if close < open: backtrack(current + ‘)’, open, close + 1) backtrack(“”, 0, 0) return result# Test the functionprint(generateParentheses(3)) 5. C# using System;using System.Collections.Generic;public class Solution { public void GenerateParentheses(int n, int open, int close, string current, List<string> result) { if (open == n && close == n) { result.Add(current); return; } if (open < n) { GenerateParentheses(n, open + 1, close, current + “(“, result); } if (close < open) { GenerateParentheses(n, open, close + 1, current + “)”, result); } } public List<string> GenerateParenthesis(int n) { List<string> result = new List<string>(); GenerateParentheses(n, 0, 0, “”, result); return result; } public static void Main() { Solution solution = new Solution(); List<string> result = solution.GenerateParenthesis(3); foreach (string s in result) { Console.WriteLine(s); } }} 6. JavaScript var generateParenthesis = function(n) { const result = []; function backtrack(current, open, close) { if (open === n && close === n) { result.push(current); return; } if (open < n) { backtrack(current + ‘(‘, open + 1, close); } if (close < open) { backtrack(current + ‘)’, open, close + 1); } } backtrack(“”, 0, 0); return result;};// Test the functionconsole.log(generateParenthesis(3)); Conclusion: