46.Permutations

46. Permutations

题目地址

https://www.lintcode.com/en/problem/permutations/

https://leetcode.com/problems/permutations/

题目描述

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

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码

Approach #1 Recursion

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) return result; 

     List<Integer> list = new ArrayList<Integer>();
     dfs(nums, list, result);

    return result;
  }

  private void dfs(int[] nums, List<Integer> list, List<List<Integer>> result) {
    if (list.size() == nums.length) {
      result.add(new ArrayList<Integer>(list));
      return;
    }

    for (int i = 0; i < nums.length; i++) {
      if (list.contains(nums[i])) continue;
      list.add(nums[i]);
      dfs(nums, list, result);
      list.remove(list.size() - 1);
    }
  }

}

Approach #2 Recursion

public class Solution {
  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> numsList = new ArrayList<Integer>();

    if (nmus == null) {
      return result;
    } else {
      // convert int[] to List<Integer>
      for (int item : nums) numsList.add(item);
    }

    if (nums.length <= 1) {
      result.add(numsList);
      return result;
    }

    for (int i = 0; i < nums.length; i++) {
      int[] numsNew = new int[nums.length - 1];
      System.arraycopy(nums, 0, numsNew, 0, i);
      System.arraycopy(nums, i + 1, numsNew, i, nums.length - i - 1);
    }

  }
}

Approach Backtrack

public class Solution {
  public void backtrack(int n, ArrayList<Integer> nums,
                       List<List<Integer>> output,
                       int first) {
    if (first == n)
      output.add(new ArrayList<Integer>(nums));
    for (int i = first; i < n; i++) {
      Collections.swap(nums, first, i);
      backtack(n, nums, output, first + 1);
      Collections.swap(nums, first, i);
    }
  }

  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> output = new LinkedList();

    ArrayList<Integer> nums_1st = new ArrayList<Integer>();
    for (int num: nums)
      nums_1st.add(num);

    int n = nums.length;
    backtrack(n, nums_1st, output, 0);
    return output;
  }
}

Approach 3: 字典序

public class Solution {
  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>();
    if (nums == null || nums.length == 0) return result;

    int[] perm = Arrays.copyOf(nums, nums.length);
    // sort first
    Arrays.sort(perm);

    while (true) {
      List<Integer> tempList = new ArrayList<Integer>();
      for (int i: perm) tempList.add(i);
      result.add(tempList);

      // step1: search the last perm[k] < perm[k+1] 
      int k = -1;
      for (int i = perm.length - 2; i >= 0; i--) {
        if (perm[i] < perm[i + 1]) {
          k = i;
          break;
        }
      }
      // if current rank is the largest, exit while loop
      if (k == -1) break;

      // step2: search the first perm[k] < perm[l]
        int l = perm.length - 1;
      while (l > k && perm[l] <= perm[k]) l--;

      // step3: swap perm[k] with perm[l]
      int temp = perm[k];
      perm[k] = perm[l];
      perm[l] = temp;

      // step4: reverse between k+1 and perm.length-1
      reverse(perm, k+1, perm.length - 1)
    }

        return result;
  }

  private void reverse(int[] nums, int left, int right) {
    for (int l = left, r = right; l < r; l++, r--) {
      int temp = nums[l];
      nums[l] = nums[r];
      nums[r] = temp;
    }
  }

}