4.1 All permutations

Assumption: no duplicate letters

Input: String input with n letters {abc}

Output: List<String> all permutations

Solution:

1. n levels in the recursion tree, each level considers one position

2. states: each time there's one less position to consider

TC: n * (n-1) * (n-2) *... * 1 = O(n!)

SC: O(n)

public List<String> permutation(String input) {
  List<String> res = new ArrayList<>();
  //corner case
  if (input == null) {
    return res;
  }
  char[] array = input.toCharArray();
  helper(array, 0, res);
  return res;
}

private void helper(char[] array, int index, List<String> res) {
  //base case
  if (index == array.length) {
    res.add(new String(array));
    return;
  }

  for (int i = index; i < array.length; i++) {
    swap(array, index, i);
    helper(array, index + 1, res);
    swap(array, index, i);
  }
}

private void swap(){...}