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

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

Example:

Input: [1,2,3]

第一种我随手写的一个深度优先的算法

public List
   
    
     > permute(int[] nums) {
           List
     
      
       > result = new ArrayList();        DFS(result, nums, new ArrayList<>());        System.out.println(result);        return result;    }    public void DFS(List
       
        
         > result, int[] nums, List
         
           list) { if(nums.length ==0){ result.add(list); } for (int i = 0; i < nums.length; i++) { List newList = new ArrayList(list); newList.add(nums[i]); DFS(result, removeIndex(nums,i),newList); } } public int[] removeIndex(int[] arr, int n) { int[] newArr = Arrays.copyOfRange(arr,0,arr.length); //把最后一个元素替代指定的元素 newArr[n] = newArr[newArr.length - 1]; //数组缩容 newArr = Arrays.copyOf(newArr, newArr.length - 1); return newArr; }
         
        
       
      
     
    
   

后面看了题解报告，发现回溯后的深度优先，可以保存中间状态并且回溯上一个状态，在空间复杂度上有很好的的提成。

这里贴了官方题解的代码

class Solution {
     public void backtrack(int n,                        ArrayList
   
     output,                        List
    
     
      > res,                        int first) {
       // 所有数都填完了    if (first == n)      res.add(new ArrayList
      
       (output));    for (int i = first; i < n; i++) {
         // 动态维护数组      Collections.swap(output, first, i);      // 继续递归填下一个数      backtrack(n, output, res, first + 1);      // 撤销操作      Collections.swap(output, first, i);    }  }  public List
       
        
         > permute(int[] nums) { List
         
          
           > res = new LinkedList(); ArrayList
           
             output = new ArrayList
            
             (); for (int num : nums) output.add(num); int n = nums.length; backtrack(n, output, res, 0); return res; }}
            
           
          
         
        
       
      
     
    
   

转载地址：http://dvwxi.baihongyu.com/