题目

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

示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路

排列类型的题目，暴力穷举所有排列，想到用回溯。

回溯模板

def backtrack(nums, path){
    // base case
    if (路径走完) {
        讲路劲加入结果集;
        return;
    }
    遍历所有选择
        选择1加入path
        backtrack(nums, path)
        选择1移出path
}

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, new ArrayList<Integer>());
        return res;
    }
    public void backtrack(int[] nums, List<Integer> path) {
        // base case
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 遍历所有选择
        for (int n : nums) {
            if (path.contains(n)) { // 检查path中是否有n话费O(n)时间，耗时，可以优化
                continue;
            }
            path.add(n);
            backtrack(nums, path);
            path.remove(path.size() - 1);
        }
    }
}

优化

上面的代码用arrayList.contains(n)检查path中是否已经有当前元素n，耗时O(n)。
如果改用visited数组，用空间换时间，可以优化这一部分的时间为O(1)。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, new ArrayList<Integer>(), new boolean[nums.length]);
        return res;
    }
    public void backtrack(int[] nums, List<Integer> path, boolean[] visited) {
        // base case
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 遍历所有选择
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {  // 用visited数组判断是否用过当前选择，O(1)
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            backtrack(nums, path, visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}