Created
February 23, 2021 08:00
-
-
Save CaffeineShawn/2d1fad220560160e8f7c0562f86ce7ce to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package com.company; | |
| import java.io.OutputStream; | |
| import java.lang.ref.SoftReference; | |
| import java.util.*; | |
| import java.util.logging.Level; | |
| public class Main { | |
| public static void main(String[] args) { | |
| Solution solution = new Solution(); | |
| System.out.println(solution.generateParenthesis(4)); | |
| } | |
| } | |
| class Solution { | |
| public List<String> generateParenthesis(int n) { | |
| List<String> res = new ArrayList<>(); | |
| StringBuilder sb = new StringBuilder(); | |
| helper(res, sb, 0, 0, 2); | |
| return res; | |
| } | |
| private void helper(List<String> res, StringBuilder sb, int lCount, int rCount, int max) { | |
| if (sb.length() == max * 2) { | |
| res.add(sb.toString()); | |
| } | |
| int len = sb.length(); | |
| if (lCount < max) { | |
| helper(res, sb.append('('), lCount + 1, rCount, max); | |
| sb.setLength(len); | |
| } | |
| if (rCount < lCount) { | |
| helper(res, sb.append(')'), lCount, rCount + 1, max); | |
| sb.setLength(len); | |
| } | |
| } | |
| } | |
| //While using StringBuilder, we need to add the quote .setLength to remove the added char, so that the StringBuilder backs to its former state and that's how we do backtracking. | |
| // Input: n = 3 | |
| // Output: ["((()))","(()())","(())()","()(())","()()()"] | |
| // | |
| // Input: n = 1 | |
| // Output: ["()"] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment