全排列

发表于

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

示例:

输入: [1,2,3]
输出:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
链接：https://leetcode-cn.com/problems/permutations

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public  List<List<Integer>> permute(int[] nums){
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(len==0){
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[len];
        dfs(nums,len,0,path,used,res);
        return res;


    }

    private  void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, 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.addLast(nums[i]);
            used[i] = true;
            dfs(nums, len, depth+1, path, used, res);//dfs一定要写在for循环里面。。。。
            //回溯。。。。前面操作干了什么，就要反操作
            path.removeLast();
            used[i] = false;
        }
        /*这样写是错的。他只会返回一个结果。。。
        for(int i=0; i<len; i++){
            if(used[i])
                continue;
            path.addLast(nums[i]);
            used[i] = true;
            break;
        }
        dfs(nums, len, depth+1, path, used, res);//dfs一定要写在for循环里面。。。。
        //回溯。。。。
        path.removeLast();
        used[i] = false;
        */
        
    }
}