Generate all permutations of a string in Java

How would you solve the problem recursively ? 

Suppose you have a permutation(n-1) which returns all permutations of size n-1. You will 

pass  
for (int i = 0; i < n; i++)
           permutation(str.substring(0, i) + str.substring(i+1, n)); 

Then to every returned string you will add str.charAt(i).

So you have to deal with an array of strings in return type.

Instead you pass the str.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);

        }

    }