LeetCode 46. 全排列

46. 全排列

解题思路

用全局路径数组记录当前排列，used 数组标记已使用元素，每次递归选一个未使用的数字加入路径，递归到底时拷贝路径存入结果「引用传递」，回溯时撤销选择尝试下一个可能「恢复现场」

参考代码

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    boolean[] used;

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

    private void dfs(int[] nums) {
        if(path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i ++) {
            if(used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}