Permutations

Problem:

Given a collection of distinct letters, return all possible permutations.

For Example:

Given: [a,b,c]
the permutations are:
[
  [a,b,c],
  [a,c,b],
  [b,a,c],
  [b,c,a],
  [c,a,b],
  [c,b,a]
]

Solution:

With backtracking, we can find the permutations. 

There are N! number of possible permutations, the time complexity will be bigger than O(N!). It will be bigger because we have to generate all those temporary substrings as parameters for recursive call. The total number of possible substrings is sum(P(N,k)) where k range from 1 to N. The sum(P(N,k)) is the number of all possible substrings by randomly picking k letter from total of N letters to form a string.
since P(N,k) = N!/(N-k)! <= N!, the sum(P(N,k)) <= N*N!.
As a result, the time complexity is between O(N!) and O(N*N!)

The since we generated many substrings as parameters for recursive calls, and java string pool did internal caching, the space complexity is bounded by the total number of possible substrings, which is less than O(N*N!).

class Solution {
  public static void permutations(String s, String remains) {
    if(remains.isEmpty()) {
      System.out.println(s);
      return;
    }
    for(int i = 0; i < remains.length(); i++) {
      char c = remains.charAt(i);
      permutations(s + c, remains.substring(0, i) + remains.substring(i+1));  //take out a character
    }
  }

  public static void main(String[] args) {
    permutations("", "abc");
  }
}

time complexity O(N!) to O(N*N!), space complexity O(N*N!)

Use string to do the permutations is easy, however it took extra space to store temporary strings, we can use a reusable char array to avoid extra space.

class Solution {
  public static void permutations(char[] orig, int n) {
    if(n == orig.length) {
      System.out.println(new String(orig));
      return;
    }
    for(int i = n; i < orig.length; i++) {
      swap(orig, n, i);
      permutations(orig, n+1);
      swap(orig, n, i);  //restore original array
    }
  }
 
  private static void swap(char[] orig, int i, int j) {
    char tmp = orig[i];
    orig[i] = orig[j];
    orig[j] = tmp;
  }
 
  public static void main(String[] args) {
    permutations("abc".toCharArray(), 0);
  }
}

time complexity O(N!) to O(N*N!), space complexity O(N) for the char array.

see also: number permutations with restrictions