Leetcoder - Distinct Subsequences (recursion)

 Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.


public class Solution {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> positions = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<T.length();i++) {
            char c = T.charAt(i);
            ArrayList<Integer> position = new ArrayList<Integer>();
            for(int j = 0;j<S.length();j++) {
                char c2 = S.charAt(j);
                if(c2==c) {
                    position.add(j);
                }
            }
            if(position.size()==0) {
                return 0;
            }
            Collections.reverse(position);
            positions.add(position);
        }
        return permuate(positions, 0, -1, 0);
    }
 
    private int permuate(ArrayList<ArrayList<Integer>> positions, int idx, int last, int amount) {
        ArrayList<Integer> position = positions.get(idx);
        for(int p : position) {
            if(p>last) {
                if(idx==positions.size()-1) {
                    amount++;
                } else {
                    amount = permuate(positions, idx+1, p, amount);
                }
            } else {
            break;
            }
        }
        return amount;
    }
}

Can't go through the time limit...Need DP...