class Solution {

    //["((()))","(()())","(())()","()(())","()()()","())(()"] wrong case --> change right > left  the numebr of bracket is the invariant

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        //back((new StringBuilder()).append('('),2*n, 1, n, n);

        back((new StringBuilder()), 2*n, 0, n, n);

        return res;

    }

    void back(StringBuilder temp, int n, int pos, int left, int right){//pos start from 1

        if(pos >= n){

            //temp.append(")"); // problem from here

            System.out.println(pos);

            res.add(temp.toString());

            return;

        }

        if(left > 0 ){

            temp.append("(");

            back(temp,n, pos+1, left-1, right);

            temp.setLength(temp.length()-1);

        }

        if(right >  left ){

            temp.append(")");

            back(temp, n, pos+1, left, right-1);

            temp.setLength(temp.length()-1);

        }

    }

}

class Solution {

    //invariant rule: each number are

    // use the immuniateble of String

    List<String> res = new ArrayList<String>();

    public List<String> restoreIpAddresses(String s) {

        back(0, s, new String(), 0);

        return res;

    }

    void back(int next, String s, String str , int num){ //num: there are only three dots.

        if(num == 3){

            //if(next==s.length()) return;

            if(!valid(s.substring(next, s.length()))) return;

            res.add(str+s.substring(next, s.length()));

            return;

        }

        //for each step, move one digit or two or three

        for(int i = 1; i <=3; i++ ){

            //check string

            if(next+i > s.length()) continue;

            String sub = s.substring(next, next+i);//

            if(valid(sub)){

                back(next+i, s, str+sub+'.', num+1);

            }

        }

    }

    boolean valid(String sub){

        if(sub.length() == 0 || sub.length()>=4) return false;

        if(sub.charAt(0) == '0') {

            //System.out.println(sub.equals("0"));

            return sub.equals("0"); // not check '0' weired

        }

        int num = Integer.parseInt(sub);

        if(num >255 || num <0) return false;

        else return true;

    }

}

class Solution {

    //check palindrome, divide into small problems:

    List<List<String>> res = new ArrayList<List<String>>();

    public List<List<String>> partition(String s) {

        back(s, new ArrayList<String>());

        return res;

    }

    void back(String s,  List<String> list){

        if(s.length()==0){

            List<String> temp = new ArrayList<>(list);

            res.add(temp);

            return ;

        }

        for(int i = 0; i<s.length(); i++){//divide s into su and sub

            String su = s.substring(0, i+1);

            String sub = s.substring(i+1, s.length());

            if(isPalindrome(su)){

                list.add(su);

                back(sub,list);

                list.remove(list.size()-1);

            }

        }

    }

    boolean isPalindrome(String su){

        if(su.length()==0){

            return true;

        }else {

            int i =0 , j = su.length()-1;

            while(i<j){

                if(su.charAt(i) != su.charAt(j)) return false;

                i++; j--;

            }

            return true;

        }

    }

}