## All permutations of a string

Write a method to compute all permutations of a string.

My initial thoughts:

• Base case: the string is a single character, the only permutation is itself.
• Recursion: all permutations of size $n$ can be obtained by insert the first character $S[0]$ into all the possible positions of permutations of size $n-1$.

My initial codes:

```	public static Set<String> allPermutationsOfString(String s) {
if (s.length() == 1) {
Set<String> result = new HashSet<String>();
return result;
} else {
Set<String> result = new HashSet<String>();
char c = s.charAt(0);
Set<String> subPermutations = allPermutationsOfString(s
.substring(1));
for (String permutation : subPermutations) {
// String newPermutation = new String();
for (int i = 0; i < permutation.length(); ++i) {
String newPermutation = permutation.substring(0, i) + c
+ permutation.substring(i);
}
}
return result;
}
}

It doesn’t work as expected.

INPUT: “abc”
EXPECTED OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba”
ACTUAL OUTPUT: “abc”, “bac”
CORRECTION: The highlighted line 13 should be revised to:
for (int i = 0; i <= permutation.length(); ++i) {

Solution:
public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) { // error case
return null;
} else if (s.length() == 0) { // base case
return permutations;
}
char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
}
}
return permutations;
}

public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}

Comments: exactly the same as mine except that it handles error case where string is null.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27ff02c3019', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27ff02c3066',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27ff02c3069',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});