The leetcode-practice from fionn88

leetcode-practice's Introduction

Todo

stack

84. Largest Rectangle in Histogram

sliding window

239. Sliding Window Maximum.py

Retry Todo

Arrays & Hashing

238. Product of Array Except Self

Two Pointer

42. Trapping Rain Water
11. Container With Most Water
15. 3Sum

Sliding Window

3. Longest Substring Without Repeating Characters
424. Longest Repeating Character Replacement
567. Permutation in String
76. Minimum Window Substring
239. Sliding Window Maximum

Stack

155. Min Stack
22. Generate_Parentheses
853. Car Fleet

Binary Search

74. Search a 2D Matrix
875. Koko Eating Bananas
33. Search in Rotated Sorted Array
981. Time Based Key-Value Store
4. Median of Two Sorted Arrays

Linked List

21. Merge Two Sorted Lists
206. Reverse Linked List
143. Reorder List
19. Remove Nth Node From End of List

leetcode-practice's People

Contributors

Watchers

leetcode-practice's Issues

22. Generate_Parentheses Problem

Time Complexity：O(n^2)
Space Complexity：O(1)
Approach 1：Generate all possible combinations of parentheses using a recursive backtracking approach.
Q: Why does this generate all possible combinations?

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        def backtrack(s, left, right):
            # Check the validity of parentheses.
            if len(s) == 2 * n:
                result.append(s) 
                return
            if left < n:
                backtrack(s + '(', left + 1, right)
            if right < left:
                backtrack(s + ')', left, right + 1)
        # Starting from an empty string, recursively add left and right parentheses.
        backtrack('', 0, 0)
        return result

Recommend Projects