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.