本文共 2419 字，大约阅读时间需要 8 分钟。

LeetCode第46题思悟——全排列（permutations）

知识点预告

1. 少做无用功；
2. Collections.swap API的使用；

题目要求

给定一个没有重复数字的序列，返回其所有可能的全排列。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutations

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutations

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

不断在i的位置上填充数据，然后接着填充下一个空位；当不需要填充数字的时候，

public List
   
    
     > permute(int[] nums) {
   	List
     
      
       > results=new ArrayList<>();	boolean[] books=new boolean[nums.length];	List
       
         start;	List
        
         
          > startList=new ArrayList<>(); for(int i=0;i
          
           (nums.length); start.add(nums[i]); startList.add(start); books[i]=true; results.addAll(stepForward(nums,books,startList,nums.length-1)); books[i]=false; startList.remove(start); } return results;}public List
           
            
             > stepForward(int[]nums,boolean[] books, List
             
              
               > products,int needNum){ if(needNum==0){ return products; } int restNum=needNum; List
               
                
                 >nextToFill=products; List
                 
                  
                   >currentToFill; List
                   
                    
                     >result=new ArrayList<>(); for(int i=0;i
                     
                      0){ nextToFill= new ArrayList<>(currentToFill.size()); for(List
                      
                        list:currentToFill){ nextToFill.add(new ArrayList<>(list)); list.add(nums[i]); } }else { for (List
                       
                         list : currentToFill) { list.add(nums[i]); } } result.addAll(stepForward(nums,books,currentToFill,needNum-1)); books[i]=false; } } return result;}
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

优秀解法

public void backtrack(int n,					  ArrayList
   
     nums,					  List
    
     
      > output,					  int first) {
   	// if all integers are used up	if (first == n)		output.add(new ArrayList
      
       (nums));	for (int i = first; i < n; i++) {
   		// place i-th integer first 		// in the current permutation		Collections.swap(nums, first, i);		// use next integers to complete the permutations		backtrack(n, nums, output, first + 1);		// backtrack		Collections.swap(nums, first, i);	}}public List
       
        
         > permute(int[] nums) { // init output list List
         
          
           > output = new LinkedList(); // convert nums into list since the output is a list of lists ArrayList
           
             nums_lst = new ArrayList
            
             (); for (int num : nums) nums_lst.add(num); int n = nums.length; backtrack(n, nums_lst, output, 0); return output;}
            
           
          
         
        
       
      
     
    
   

差异分析

优秀解法采用不断交换数字；当交换点到达末尾时，产生一个全排列；实际上到达交换点也意味着该位置的数字已经被确定；

填充的问题在于，每产生一个分支，就要执行一遍list的复制；中间状态的结果也会进行复制；而交换则只需要在产生结果时执行一次复制；

知识点小结

1. 少做无用功；
2. Collections.swap API的使用；