// Permutation problem, similar to permutation of strings. Runs in O(2^n), where n is array length,
// similar the one for strings.
// The main gotcha is avoiding array copy for each iteration, that is why we propagate indices
// 'start' and 'end' for each recursion.
public class Solution {
  public List<List<Integer>> permute(int[] nums) {
    return permute(nums, 0, nums.length - 1);
  }

  private List<List<Integer>> permute(int[] nums, int start, int end) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (start == end) {
      List<Integer> list = new ArrayList<Integer>();
      list.add(nums[start]);
      res.add(list);
    } else if (start < end) {
      List<List<Integer>> out = permute(nums, start + 1, end);
      for (List<Integer> arr : out) {
        for (int i = 0; i <= arr.size(); i++) {
          List<Integer> ext = new ArrayList<Integer>();
          for (int p = 0; p < i; p++) ext.add(arr.get(p));
          ext.add(nums[start]);
          for (int p = i; p < arr.size(); p++) ext.add(arr.get(p));
          res.add(ext);
        }
      }
    }
    return res;
  }
}

@@ -66,11 +66,10 @@
 n O(
-2%5E
 n
+!
 ), w
@@ -1111,8 +1111,945 @@
 ;%0A  %7D%0A%7D%0A
+%0A// Slightly faster solution (based on Leetcode runtime distribution, beats 67.76%25)%0A// We use only one index to indicate current position, everything to the left has already been%0A// permuted, to the right - yet to be processed.%0Aclass Solution %7B%0A  public List%3CList%3CInteger%3E%3E permute(int%5B%5D nums) %7B%0A    return permute(nums, nums.length - 1);%0A  %7D%0A%0A  private List%3CList%3CInteger%3E%3E permute(int%5B%5D nums, int pos) %7B%0A    List%3CList%3CInteger%3E%3E res = new ArrayList%3CList%3CInteger%3E%3E();%0A    if (pos == 0 && pos %3C nums.length) %7B%0A      List%3CInteger%3E tmp = new ArrayList%3CInteger%3E();%0A      tmp.add(nums%5Bpos%5D);%0A      res.add(tmp);%0A    %7D else if (pos %3C nums.length) %7B%0A      List%3CList%3CInteger%3E%3E arr = permute(nums, pos - 1);%0A      for (List%3CInteger%3E t : arr) %7B%0A        for (int i = 0; i %3C= t.size(); i++) %7B%0A          List%3CInteger%3E cp = new ArrayList%3CInteger%3E(t);%0A          cp.add(i, nums%5Bpos%5D);%0A          res.add(cp);%0A        %7D%0A      %7D%0A    %7D%0A    return res;%0A  %7D%0A%7D%0A

add permutations solution