Java implementation based on the idea of stack


  • 1
    S

    fpNumRemain: is the number of front parenthesis remained;
    bpNum: is the number of back parenthesis needed to put;

    My implementation is based on the idea of stack.
    Whenever you put one front parenthesis, you need to put one back parenthesis sometime later, so you add bpNum by 1 while subtract 1 from fpNumRemain (kinda like push back parenthesis into a stack, but there's no need to really do so)

    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> list = new LinkedList<String> ();
            generate(n, 0, "", list);
            return list;
        }
        
        public void generate(int fpNumRemain, int bpNum, String str, List<String> list){
            if(fpNumRemain == 0 && bpNum == 0){
                list.add(str);
                return;
            }
            String tempStr;
            if(fpNumRemain > 0){
                tempStr = str + "(";
                generate(fpNumRemain - 1, bpNum + 1, tempStr, list);
            }
            if(bpNum > 0){
                tempStr = str + ")";
                generate(fpNumRemain , bpNum - 1, tempStr, list);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.