Publicis Sapient interview question

They asked me to implement a recursive solution for generating all permutations of a string. I explained my approach using backtracking and discussed time complexity.