partion

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> st= new ArrayList<>();
        List<String> path=new ArrayList<>();
        func(0,s,st,path); 
        return st;
    }

    public static void func(int index,String str,List<List<String>>st,List<String> path)
    {

       if(index==str.length())
       {
          st.add(new ArrayList<>(path));
          return;
       }

       for(int i=index;i<str.length();i++)
       {
           if(check(index,i,str))
           {
               path.add(str.substring(index,i+1));
               func(i+1,str,st,path);
               path.remove(path.size()-1);
           }
       }   
    }

    public static boolean check(int index,int i,String str)
    {
        while(index<i)
        {
            char ch1= str.charAt(index);
            char ch2= str.charAt(i);
            if(ch1!=ch2)
            {
               return false; 
            }
            index++;
            i--;
        }
        return true;


    }
}