[Leetcode] Permutations

时间：2015-08-12 16:14:31 收藏：0 阅读：212

I have two solutions for this problem, the first one is from the undergraduate stage, the second one is from the CTCI (permute string)

The common point of the two methods lies in the recursive method they both used.

1. Enumerate the head

First method sounds more efficient. For the integer list, if will enumerate the first integer in the range of the current list.

For example, [1,2,3,4,5]

first integer can be:

1, [2,3,4,5]

2,[3,4,5] 3,[2,4,5] 4,[2,3,5] 5,[2,3,4]

2, [1,3,4,5]

3, [1,2,4,5]

4, [1,2,3,5]

5, [1,2,3,4]

when the head is chosen, the left sub list can be regarded as a smaller problem with the same method. The recursive function will return when the last index reached. We should use a list to track the

selected element in each layer of the recursive.

The best run time of this method is 300ms

 1 import java.util.*;
 2 
 3 public class Solution {
 4     private void backtrack(List<List<Integer> > lists, int []nums, int index){
 5         if(index==nums.length){
 6             List<Integer> tl=new LinkedList<Integer>();
 7             for(int element: nums){
 8                 tl.add(element);
 9             }
10             lists.add(tl);
11         }
12         for(int i=index;i<nums.length;i++){
13             int tmp=nums[i];
14             nums[i]=nums[index];
15             nums[index]=tmp;
16             backtrack(lists,nums,index+1);
17             tmp=nums[i];
18             nums[i]=nums[index];
19             nums[index]=tmp;
20         }
21     }
22     public List<List<Integer>> permute(int[] nums) {
23         List<List<Integer> > lists = new LinkedList<List<Integer> >();
24         backtrack(lists,nums,0);
25         return lists;
26     }
27 }

2. insert method

The second method uses the insert strategy.

First we remove the first integer, then permute the remain list and insert the removed element into the premutation result.

The best run time of this method is 336ms

 1 public class Solution {
 2     private List<List<Integer>> permuteutil(int []nums,int index){
 3         List<List<Integer>> listres = new LinkedList<List<Integer>>();
 4         if(index==nums.length-1) {
 5             List<Integer> listnew = new LinkedList<Integer>();
 6             listnew.add(nums[index]);
 7             listres.add(listnew);
 8             return listres;
 9         }
10         int first = nums[index];
11         List<List<Integer>> leftperm = permuteutil(nums,index+1);
12         for(List<Integer> tmplist: leftperm){
13             // the insert position should include the tail next position ,just the tmplist.size().
14             for(int i=0;i<=tmplist.size();i++){
15                 List<Integer> listnew = new LinkedList<Integer>();
16                 listnew.addAll(tmplist);
17                 listnew.add(i,first);
18                 listres.add(listnew);
19             }
20         }
21         return listres;
22     }
23     public List<List<Integer>> permute(int[] nums) {
24         return permuteutil(nums,0);
25     }
26 }

原文：http://www.cnblogs.com/deepblueme/p/4724662.html