Another hint, although the Backtracking works well for this problem. We can also use Dynamic Programming to solve Permutation.

/* Dynamic Programming */ private Set<String> permutation(String letters) { Set<String> result = new HashSet<>(); if (letters.length() == 0) { return result; } if (letters.length() == 1) { result.add(letters); return result ; } char c = letters.charAt(0); Set<String> subSet = permutation(letters.substring(1)); for (String str : subSet) { int len = str.length(); for (int i = 0; i <= len; i++) { result.add(str.substring(0,i) + c + str.substring(i,len)); } } return result; }Palindrome Permutation II