牛客NC26 括号生成【中等 递归 Java,Go,PHP】

题目

题目链接：
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca

思路

答案链接：https://www.lintcode.com/problem/427/solution/16924

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> ans = new ArrayList<>();
        dfs(0, 0, "", n, ans);
        return ans;
    }

    public void dfs(int cnt1, int cnt2, String str, int n, ArrayList<String> ans) {
        if (cnt1 > n || cnt2 > n) return; // cnt1和cnt2不能大于n
        if (cnt1 < cnt2) return; //左括号数量不能多余右括号
        if (cnt1 == n && cnt2 == n) {
            ans.add(new String(str));
            return;
        }

        dfs(cnt1 + 1, cnt2, str + "(", n, ans); //搜索加左括号的情况
        dfs(cnt1, cnt2 + 1, str + ")", n, ans); //搜索加右括号的情况
    }
}

参考答案Go

package main

import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @return string字符串一维数组
 */
func generateParenthesis(n int) []string {
	ans := []string{}
	dfs(0, 0, "", n, &ans)
	return ans
}

func dfs(cnt1 int, cnt2 int, str string, n int, ans *[]string) {
	if cnt1 > n || cnt2 > n { // cnt1和cnt2不能大于n
		return
	}
	if cnt1 < cnt2 { //左括号数量不能多余右括号
		return
	}
	if cnt1 == n && cnt2 == n {
		s := str
		*ans = append(*ans, s)
		return
	}

	str1 := fmt.Sprintf("%s%s", str, "(")
	dfs(cnt1+1, cnt2, str1, n, ans) //搜索加左括号的情况
	str2 := fmt.Sprintf("%s%s", str, ")")
	dfs(cnt1, cnt2+1, str2, n, ans) //搜索加右括号的情况
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return string字符串一维数组
 */
function generateParenthesis( $n )
{
     $ans = array();
    dfs(0,0,'',$n,$ans);
  return $ans;
}

function dfs($cnt1,$cnt2,$str,$n,&$ans){
    if ($cnt1 >$n || $cnt2 >$n) { // cnt1和cnt2不能大于n
        return;
	}
    if ($cnt1 < $cnt2) { //左括号数量不能多余右括号
        return;
	}
    if ($cnt1 == $n && $cnt2 == $n) {
       array_push($ans,$str);
		return;
	}


	dfs($cnt1+1, $cnt2, $str.'(', $n, $ans) ;//搜索加左括号的情况
	dfs($cnt1, $cnt2+1, $str.')', $n, $ans); //搜索加右括号的情况
}