Detailed explanation from the view of recursion tree


  • 0

    Re: Easy to understand Java backtracking solution

    I checked out several solutions. They're very nice and seems like a magic of recursion which I cannot understand and make me upset.
    Then I try to dig into this problem and see how can I come up nice solution like them.

    For this kind of combinatorial problem, typically we use Tree to represent the search space and generate all possible solutions by search.
    Tree is so powerful which is able to represent efficient dicitionary (BST), prefix compression (Trie) or recursion.
    Essentially, it is the representation of execution of program. (In Theory of Computation, it's called Configuration Graph.)
    Therefore, recursion tree is just a special case but sufficient for analyzing and solving this problem.

    So we use Tree to represent the entire search space. Each node is the state of program at that point. What's the state of this problem?
    Since we'd like to generate all valid parenthesis, the state we concern is just the String we concat by now.
    Then each edge is the choice (precisely, one transition from Transition Function). We only have two options: concat '('' or ')'.
    Thus we can draw the entire tree as follows (which is unique, right?).

    0_1482412702046_Untitled Diagram (1).png

    The characteristic of the Tree is due to that of the problem:

    • We can choose '(' only if we didn't exceed the max limit
    • We can choose ')' only if there aren't more )' than '(' by now (otherwise we cannot fix this no matter how we iterate in the following).

    Now all those nice solutions seem to be very clear. They're different just because they use different search technique on this unique tree.
    The first and natural searching approach is DFS which is the green arrow in the diagram above.
    Since this is not a Complete Tree, we need variables (left/right or open/close) to control.
    They help us not to reach non-existing node on the Tree which means syntax wrong state such as ')((())'.

        public List<String> generateParenthesis(int n) {
            List<String> ret = new ArrayList<>();
            generate(ret, new char[n * 2], 0, 0, n, 0);
            return ret;
        }
        
        private void generate(List<String> ret, char[] str, int left, int right, int max, int i) {
            if (left == max && right == left) {
                ret.add(String.valueOf(str));
                return;
            }
            
            if (left < max) {
                str[i] = '(';
                generate(ret, str, left + 1, right, max, i + 1);
            }
            if (right < left) {
                str[i] = ')';
                generate(ret, str, left, right + 1, max, i + 1);
            }
        }
    

    At last, let's review the most upvoted solution and see if we can understand now.
    https://discuss.leetcode.com/topic/4485/concise-recursive-c-solution

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> res;
            addingpar(res, "", n, 0);
            return res;
        }
        void addingpar(vector<string> &v, string str, int n, int m){
            if(n==0 && m==0) {
                v.push_back(str);
                return;
            }
            if(m > 0){ addingpar(v, str+")", n, m-1); }
            if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
        }
    };
    

    See? They turn out to be the same. We start off with left(n)=n, right(m=0).
    Then if right > 0, we go right. If left > 0, we go left meanwhile increase right by 1.
    The blue arrow show the order of this program.


Log in to reply
 

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