I'm wondering if the scramble function can produce all the possible permutations? If yes, we can simply check if s2 is a permutatio of s1, even though it may time out.

No, it can't. Moreover, permutation check is pretty easy and would usually not time out, we just need to count if the two string has same number of each characters, if so one string is permutation of the other. It's a O(n) function.