图解

代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, 0, res, path);
        return res;
    }

    public void dfs(int[] c, boolean[] used, int level, List<List<Integer>> res, List<Integer> path){
        if(level == c.length){
            res.add(new ArrayList(path));
            return;
        }

        for(int i = 0; i < c.length; i++){
            //剪枝
            if(used[i]) continue;
            used[i] = true;
            path.add(c[i]);
            dfs(c, used, level+1, res, path);
            path.remove(new Integer(c[i]));
            used[i] = false;
        }
    }
}

dfs二刷 20200711

class Solution {

    List<List<Integer>> res = new ArrayList();
    Stack<Integer> path = new Stack();

    public List<List<Integer>> permute(int[] c) {
        boolean[] used = new boolean[c.length];
        dfs(c, used);
        return res;
    }

    public void dfs(int[] c, boolean[] used){
        if(c.length == path.size()){
            res.add(new ArrayList(path));
            return;
        }

        // 遍历每一个位置
        // 排列问题, 每一个位置可以放数组中的任意一个数, 所以指针i总是从0开始, 此时就需要加上状态数组辅助记录
        for(int i = 0; i < c.length; i++){
            if(!used[i]){
                path.push(c[i]);
                used[i] = true;
                dfs(c, used);
                used[i] = false;
                path.pop();
            }
        }
    }
}