Permutations

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

For example,

[1,2,3] have the following permutations:

  1. [
  2.   [1,2,3],
  3.   [1,3,2],
  4.   [2,1,3],
  5.   [2,3,1],
  6.   [3,1,2],
  7.   [3,2,1]
  8. ]

Solution:

  1. public class Solution {
  2.   public List<List<Integer>> permute(int[] nums) {
  3.     List<List<Integer>> res = new ArrayList<>();
  5.     if (nums.length == 0) 
  6.       return res;
  8.     res.add(new ArrayList<Integer>(Arrays.asList(nums[0])));
  10.     for (int i = 1; i< nums.length; i++) {
  11.       List<List<Integer>> next = new ArrayList<>();
  13.       for (int j = 0; j <= i; j++) {
  14.         for (List<Integer> list : res) {
  15.           // make a copy of existing perm
  16.           List<Integer> copy = new ArrayList<>(list);
  17.           copy.add(j, nums[i]);
  18.           next.add(copy);
  19.         }
  20.       }
  22.       res = next;
  23.     }
  25.     return res;
  26.   }
  27. }