title: Recursion Question with Valid Parenthesis
body: <p>I am trying to understand this solution for generating all valid parentheses.</p>
  <p>The part I don't understand is how the recursion can find ALL of the different combinations. When I debug through the code, I put a watch on the integers &quot;left&quot; and &quot;right.&quot; With the input of 2 in generateParenthesis, after &quot;ans&quot; is populated with 1 valid parenthesis, at &quot;return ans&quot; I see the variable &quot;right&quot; decrease making the if statement &quot;right &lt; left&quot; valid. How does the variable &quot;right&quot; decrease like that when I never specifically set it to do so? To put it simply, how is recursion able to find all the cases of valid parenthesis, not just one in this situation?</p>
  <p>Below I included the question along with an online Python Debugger to see what I'm talking about.
  <a href="https://onlinegdb.com/LMNYtq3iR" rel="nofollow noreferrer">https://onlinegdb.com/LMNYtq3iR</a></p>
  <p><a href="https://leetcode.com/problems/generate-parentheses/" rel="nofollow noreferrer">https://leetcode.com/problems/generate-parentheses/</a></p>
  <pre><code>def generateParenthesis(N):
     ans = []
     S = ''
     left = 0
     right = 0
     ans = backtrack(N, S, left, right, ans)
  
  def backtrack(N, S, left, right, ans):
     print(left)
     if len(S) == 2 * N:
        ans.append(S)
     if left &lt; N:
        backtrack(N, S+'(', left+1, right, ans)
     if right &lt; left:
      backtrack(N, S+')', left, right+1, ans)
  
     return ans
      
  generateParenthesis(2)
  </code></pre>