46. 全排列

难度中等1219

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

示例:

  1. 输入: [1,2,3]
  2. 输出:
  3. [
  4.   [1,2,3],
  5.   [1,3,2],
  6.   [2,1,3],
  7.   [2,3,1],
  8.   [3,1,2],
  9.   [3,2,1]
  10. ]

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if(len==0){
            return res;
        }
        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(len,path,0,used,nums,res);
        return res;
    }
    private void dfs(int len, Deque<Integer>path,
                     int depth,boolean[] used,
                     int[] nums,
                     List<List<Integer>> res ){
        //所要找的全排列中的个数达到数组个数。
        if(depth==len){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<len;i++){
            if(used[i]){
               continue; 
            }
            path.push(nums[i]);
            used[i]= true;
            dfs(len,path,depth+1,used,nums,res);
            //回退
            path.pop();
            used[i]=false;
        }


    }

}