{"id":745,"date":"2025-07-22T13:17:20","date_gmt":"2025-07-22T07:47:20","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=745"},"modified":"2025-07-22T13:17:21","modified_gmt":"2025-07-22T07:47:21","slug":"generate-parentheses","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/","title":{"rendered":"Generate Parentheses | Leetcode 22 | Backtracking Approach"},"content":{"rendered":"\n<p>Given&nbsp;<code>n<\/code>&nbsp;pairs of parentheses, write a function to&nbsp;<em>generate all combinations of well-formed parentheses<\/em>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/generate-parentheses\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 3<br><strong>Output:<\/strong> [\"((()))\",\"(()())\",\"(())()\",\"()(())\",\"()()()\"]<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 1<br><strong>Output:<\/strong> [\"()\"]<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= n &lt;= 8<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-4c2a8699-4ee7-4031-90cf-bb6ee4fec666\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#0-solution-backtracking-approach\" style=\"\">Solution: Backtracking Approach<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/generate-parentheses\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-backtracking-approach\">Solution: Backtracking Approach<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like building a balanced structure with opening and closing brackets! For n pairs of parentheses, you need exactly n opening &#8216;(&#8216; and n closing &#8216;)&#8217; brackets. But here&#8217;s the catch &#8211; at any point, you can&#8217;t have more closing brackets than opening ones (that would be invalid like &#8220;)(&#8221; ). It&#8217;s like building with blocks where you need a foundation (opening bracket) before you can close it. We use backtracking to try placing &#8216;(&#8216; or &#8216;)&#8217; at each position, keeping track of how many &#8220;unmatched&#8221; opening brackets we have. When we complete all positions and have zero unmatched brackets, we found a valid combination!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialize Setup<\/strong>: Create an array of empty strings with length 2*n (since we need n pairs).<\/li>\n\n\n\n<li><strong>Recursive Function<\/strong>: Use a helper function that takes current index, running total of unmatched opening brackets, the brackets array, and result list.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When index reaches 2*n, check if total equals 0 (all brackets matched) &#8211; if yes, add to results.<\/li>\n\n\n\n<li><strong>Pruning Conditions<\/strong>:\n<ul class=\"wp-block-list\">\n<li>If total > n: too many unmatched opening brackets, stop this path.<\/li>\n\n\n\n<li>If total &lt; 0: more closing than opening brackets, invalid, stop this path.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Try Opening Bracket<\/strong>: Place &#8216;(&#8216; at current position, increment total (one more unmatched opening), and recurse.<\/li>\n\n\n\n<li><strong>Try Closing Bracket<\/strong>: Place &#8216;)&#8217; at current position, decrement total (match one opening bracket), and recurse.<\/li>\n\n\n\n<li><strong>Backtrack<\/strong>: The array gets overwritten naturally as we try different choices.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, index, total, brackets, result):\n        # Base case: If we've filled all positions\n        if index &gt;= len(brackets):\n            if total == 0:  # All brackets are properly matched\n                result.append(&quot;&quot;.join(brackets))  # Add valid combination\n            return\n        \n        # Pruning: Too many unmatched opening brackets\n        if total &gt; len(brackets) \/\/ 2:\n            return\n        \n        # Pruning: More closing brackets than opening (invalid)\n        if total &lt; 0:\n            return\n        \n        # Choice 1: Place opening bracket '('\n        brackets[index] = &quot;(&quot;\n        Sum = total + 1  # Increment unmatched opening count\n        self.solve(index + 1, Sum, brackets, result)\n        \n        # Choice 2: Place closing bracket ')'\n        brackets[index] = &quot;)&quot;\n        Sum = total - 1  # Decrement unmatched opening count\n        self.solve(index + 1, Sum, brackets, result)\n\n    def generateParenthesis(self, n: int) -&gt; List[str]:\n        brackets = [&quot;&quot;] * (n * 2)  # Array of size 2n for n pairs\n        result = []                # List to store all valid combinations\n        self.solve(0, 0, brackets, result)  # Start with index 0, total 0\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">total<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">brackets<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: If we&#39;ve filled all positions<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(brackets):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> total == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:  <\/span><span style=\"color: #6A9955\"># All brackets are properly matched<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                result.append(<\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">.join(brackets))  <\/span><span style=\"color: #6A9955\"># Add valid combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Pruning: Too many unmatched opening brackets<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> total &gt; <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(brackets) \/\/ <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Pruning: More closing brackets than opening (invalid)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> total &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 1: Place opening bracket &#39;(&#39;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        brackets[index] = <\/span><span style=\"color: #CE9178\">&quot;(&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Increment unmatched opening count<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, Sum, brackets, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 2: Place closing bracket &#39;)&#39;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        brackets[index] = <\/span><span style=\"color: #CE9178\">&quot;)&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Decrement unmatched opening count<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, Sum, brackets, result)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">generateParenthesis<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        brackets = [<\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">] * (n * <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">)  <\/span><span style=\"color: #6A9955\"># Array of size 2n for n pairs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = []                <\/span><span style=\"color: #6A9955\"># List to store all valid combinations<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, brackets, result)  <\/span><span style=\"color: #6A9955\"># Start with index 0, total 0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>The&nbsp;<code>solve<\/code>&nbsp;function uses backtracking to build parentheses combinations while maintaining validity through the&nbsp;<code>total<\/code>&nbsp;parameter. The&nbsp;<code>total<\/code>&nbsp;keeps track of how many opening brackets are currently &#8220;unmatched&#8221; (waiting for their closing pair). At each position, we try placing &#8216;(&#8216; (increases unmatched count) and &#8216;)&#8217; (decreases unmatched count). The key insight is the pruning: if total goes negative, we have more closing than opening brackets (invalid), and if total exceeds n, we have too many unmatched opening brackets. When we fill all positions and total equals 0, all brackets are properly matched, so we add it to results.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through n=2 (need 4 positions total):<\/p>\n\n\n\n<p><strong>Start: index=0, total=0, brackets=[&#8220;&#8221;,&#8221;&#8221;,&#8221;&#8221;,&#8221;&#8221;]<\/strong><\/p>\n\n\n\n<p><strong>Try &#8216;(&#8216; at index 0:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>brackets=[&#8220;(&#8220;,&#8221;&#8221;,&#8221;&#8221;,&#8221;&#8221;], total=1, index=1<strong>Try &#8216;(&#8216; at index 1:<\/strong><ul><li>brackets=[&#8220;(&#8220;,&#8221;(&#8220;,&#8221;&#8221;,&#8221;&#8221;], total=2, index=2<strong>Try &#8216;(&#8216; at index 2:<\/strong><ul><li>total=3 > 2 (n), prune this path<\/li><\/ul><strong>Try &#8216;)&#8217; at index 2:<\/strong><ul><li>brackets=[&#8220;(&#8220;,&#8221;(&#8220;,&#8221;)&#8221;,&#8221;&#8221;], total=1, index=3<strong>Try &#8216;(&#8216; at index 3:<\/strong><ul><li>total=2, index=4 \u2192 total\u22600, don&#8217;t add<\/li><\/ul><strong>Try &#8216;)&#8217; at index 3:<\/strong><ul><li>brackets=[&#8220;(&#8220;,&#8221;(&#8220;,&#8221;)&#8221;,&#8221;)&#8221;], total=0, index=4 \u2192 add &#8220;(())&#8221; to result<\/li><\/ul><\/li><\/ul><\/li><\/ul><strong>Try &#8216;)&#8217; at index 1:<\/strong>\n<ul class=\"wp-block-list\">\n<li>brackets=[&#8220;(&#8220;,&#8221;)&#8221;,&#8221;&#8221;,&#8221;&#8221;], total=0, index=2<strong>Try &#8216;(&#8216; at index 2:<\/strong>\n<ul class=\"wp-block-list\">\n<li>brackets=[&#8220;(&#8220;,&#8221;)&#8221;,&#8221;(&#8220;,&#8221;&#8221;], total=1, index=3<strong>Try &#8216;)&#8217; at index 3:<\/strong>\n<ul class=\"wp-block-list\">\n<li>brackets=[&#8220;(&#8220;,&#8221;)&#8221;,&#8221;(&#8220;,&#8221;)&#8221;], total=0, index=4 \u2192 add &#8220;()()&#8221; to result<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Try &#8216;)&#8217; at index 0:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>total=-1 &lt; 0, prune this path immediately<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;<code>[\"(())\", \"()()\"]<\/code><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(4^n \/ \u221an) &#8211; This is the nth Catalan number, which represents the number of valid parentheses combinations. The backtracking explores this many valid paths plus some pruned invalid ones.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) &#8211; The recursion stack depth is 2n, plus space for the brackets array.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h2>\n\n\n\n<p>This backtracking approach is like carefully building a tower with opening and closing pieces. The\u00a0<code>total<\/code>\u00a0acts like a balance meter, it goes up when you add an opening piece (creating an imbalance that needs fixing) and goes down when you add a closing piece (fixing the imbalance). You can only close what you&#8217;ve opened, and at the end, everything must be perfectly balanced (total = 0). The pruning conditions act like safety checks, preventing you from building impossible structures. It&#8217;s a beautiful example of how backtracking can generate all valid solutions while efficiently avoiding invalid paths!<\/p>\n\n\n\n<p>This problem is fantastic for understanding constraint-based generation and is a common interview question that tests your ability to think about valid states and pruning conditions.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;n&nbsp;pairs of parentheses, write a function to&nbsp;generate all combinations of well-formed parentheses. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: n = 3Output: [&#8220;((()))&#8221;,&#8221;(()())&#8221;,&#8221;(())()&#8221;,&#8221;()(())&#8221;,&#8221;()()()&#8221;] Example 2: Input: n = 1Output: [&#8220;()&#8221;] Constraints: Solution: Backtracking Approach Intuition Think of this like building a balanced structure with opening and closing brackets! For n pairs of<\/p>\n","protected":false},"author":1,"featured_media":746,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-745","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-advance-recursion","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/generate-parentheses-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/745","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=745"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/745\/revisions"}],"predecessor-version":[{"id":747,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/745\/revisions\/747"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/746"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}