How would you solve the problem recursively ? Suppose you have a permutation(n-1) which returns all permutations of size n-1. You will passfor (int i = 0; i < n; i++) permutation(str.substring(0, i) + str.substring(i+1, n));
Then to every returned string you will addstr.charAt(i).
So you have to deal with an array of strings in return type.Instead you pass thestr.charAt(i) as a part of the input itself and you dont
need to worry about concatenating it at the end. Instead when the length of the second parameter in the permutation becomes 0 you just print the first paramter. public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
} Now you have done it with strings and you are printing it. Suppose you have to return a List<List<Integer>> then how would you do it. Practise this as it will improve your collections.
public class Solution {
List<List<Integer>> ret;
public List<List<Integer>> permute(int[] num) {
ret = new LinkedList<>();
LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 0; i < num.length; i++)
numbers.add(num[i]);
LinkedList<Integer> list = new LinkedList<>();
permute(numbers, list);
return ret;
}
private void permute(List<Integer> numbers, List<Integer> list) {
if (numbers.size() == 0) {
LinkedList<Integer> newList = new LinkedList<>();
newList.addAll(list);
ret.add(newList);
return;
}
for (int i = 0; i < numbers.size(); i++) {
int candidate = numbers.get(i);
numbers.remove(i);
list.add(candidate);
permute(numbers, list);
list.remove(list.size() - 1);
numbers.add(i, candidate);
}
}
