欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode.22括号生成

程序员文章站 2024-03-21 17:37:10
...

题目来源:https://leetcode-cn.com/problems/generate-parentheses/description/

题目描述:

LeetCode.22括号生成

 算法描述:

1.这个题目可以看成是一个回溯算法。

2.只要有左括号就先将左括号添加到str字符串中进行递归,如果没有左括号,就将右括号添加到str字符串中进行递归。

直到左右括号数量都为0,说明此时找出一组解,将这组解添加到list集合中。返回到上次递归的地方找下一组解。

代码如下:

class Solution {
        public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        recursion(n,n,"",list);
        System.out.println(list);
        return list;
    }
    
    //left为剩余左括号数,right为剩余右括号数。
    public void recursion(int left,int right,String str,List<String> list){
    	//当左右括号都已匹配完毕,就返回
    	if(left==0&&right==0) {
    		list.add(str);
    		return;
    	}
    	//如果有左括号,当前字符串加上左括号,左括号个数-1进入递归
    	if(left>0) {
    		recursion(left-1,right,str+"(",list);
    	}
    	//如果当前剩余右括号个数大于左括号,当前字符串加上右括号,右括号个数-1进入递归
    	if(left<right) {
    		recursion(left,right-1,str+")",list);
    	}
    }
}