文章目錄

• 題目描述
• 代碼 & 解法

題目描述

• 先吐槽：括號題好惡心。。
• 括號有效判斷需要考慮考慮
  

代碼 & 解法

• 思路：把括號分開看，這道題和20.有效的括號其實是有差別的：這道題的括號是成對的，而20題的括號則沒有這個硬性要求。
  基于此，我們可以用這么一個思路去考慮這道題：分配一個大小為2n的括號集，其中n個是左括號，n個是右括號
• 遞歸過程中需要剪枝，遞歸結束時獲得答案。
• 結果正確性：見代碼注釋1.2.

class Solution {public List<String> generateParenthesis(int n) {/**1. 如何確保不重復：畫格子，走不同分枝肯定至少有一個格子不同。如下[x][x][o][x][x][x][o][o]也就是無論如何，不同分枝代表的字符串內容肯定不相同。2. 如何跑全：因為包括了所有左右括號組合。*/ArrayList<String> ans = new ArrayList<>();dfs(ans, n, n, "");return ans;}// ans（存儲答案）；left（左括號剩余數）；right（右括號剩余數）；now（當前字符串）public void dfs(ArrayList<String> ans, int left, int right, String now) {// 遞歸結束if (left == 0 && right == 0) {ans.add(now);}// 剪枝情況：如")"，肯定是錯誤順序。if (right < left) {return;}// 走左括號路線if(left > 0){dfs(ans, left - 1, right, now + "(");}// 走右括號路線if(right > 0){dfs(ans, left, right - 1, now + ")");}return;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】22.括号生成（Java、DFS回溯、剪枝、括号）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。