Java recursive BT solution, advices wanted!!


  • 0

    I am new to BackTracking algorithm, I read a chapter about it last night and today I pick this problem to practice, I knew that it runs very slowly. Luckily the judge system only tests 8 cases and my code is accepted. But I want to know more about BackTracking, any links can I refer to? Thanks in advance! Here is my code:

        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<>();
            if (n == 0)
                return result;
            char[] bt = new char[2 * n];
            backtracking(result, bt, 0, bt.length);
            return result;
        }
    
        public void backtracking(List<String> result, char[] bt, int k, int n) {
            char[] parentheses = {'(', ')'};
            for (char c : parentheses) {
                if (validIfAdded(bt, k, c)) {
                    if (k == n - 1) {
                        if (parenthesesValid(bt, k, true))
                            result.add(new String(bt));
                    }
                    else
                        backtracking(result, bt, k + 1, n);
                }
            }
        }
    
        // if valid after adding char c, add it, and return true, else return false
        public boolean validIfAdded(char[] sb, int k, char c) {
            sb[k] = c;
            if (parenthesesValid(sb, k, false))
                return true;
            return false;
        }
    
        public boolean parenthesesValid(char[] sb, int k, boolean strict) {
            LinkedList<Character> stack = new LinkedList<>();
            char c;
            for (int i = 0; i <= k; i++) {
                if ((c = sb[i]) == '(')
                    stack.addLast(c);
                else if (c == ')')
                    if (stack.isEmpty() || stack.getLast() != '(')
                        return false;
                    else
                        stack.removeLast();
            }
            if (strict)
                return stack.isEmpty();
            return true;
        }
    

  • 0

    Hi keZhenxu,

    I just posted another solution here:
    https://discuss.leetcode.com/topic/60131/java-solution-with-thinking-process-and-lots-of-comment
    It has a good a amount of comments. Hope it helps :)

    Generally for back tracking you need to think about 2 things:

    1. base case, aka, termination condition
    2. how to build one level up from base case, aka, how does the recursion work, what parameters does next level needs to know from previous level

Log in to reply
 

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