Given a string with no duplicate characters, return a list with all permutations of the string and all its subsets.
Examples
Set = "abc", all permutations are: ["", "a", "ab", "abc", "ac", "acb", "b", "ba", "bac", "bc", "bca", "c", "cb", "cba", "ca", "cab"].
I know how to do it if I broke up the whole thing into two parts:
But I am wondering if there is a way to write the DFS helper function to do it in just one step.
Sure. This isn't the fastest method, but it's simple and enumerates in the lexicographic order such that the input string is the minimum permutation.
private static void printPerms(char[] set, int i) {
System.out.println(new String(set, 0, i));
for (int j = i; j < set.length; j++) {
char c = set[j];
// move c to position i
for (int k = j; k > i; k--) {
set[k] = set[k - 1];
}
set[i] = c;
printPerms(set, i + 1);
// move c back to position j
for (int k = i; k < j; k++) {
set[k] = set[k + 1];
}
set[j] = c;
}
}