public static List<List<String>> partition(String s) {
        // write your code here
        int n=s.length();
        boolean[][]t=new boolean[n][n];
        for (int i=0;i<n;++i) {
            t[i][i]=true;
            if (i+1<n)
                t[i][i+1]=s.charAt(i)==s.charAt(i+1);
        }
        for (int l=2;l<=n;++l) {
            for (int i=0;i+l<n;++i) {
                if (t[i+1][i+l-1]&&s.charAt(i)==s.charAt(i+l))
                    t[i][i+l]=true;
            }
        }
        List<List<Integer>>r=new ArrayList<>();
        r.add(new ArrayList<Integer>());
        for (int i=1;i<=n;++i) {
            List<Integer>c;
            r.add(c=new ArrayList<Integer>());
            for (int j=1;i-j>=0;++j) {
                if (t[i-j][i-1])
                    c.add(i-j);
            }
        }
        List<List<String>> rel=new ArrayList<>();
        pHelper(s,r,n, new ArrayList<>(), rel);
        return rel;
    }