Microsoft Interview Question

Given an input string, write an efficient program that will print all of it's permutations.