46. 全排列

Problem: 46. 全排列

思路

本题可以用回溯的思路来解决。对于搜索函数dfs，我们记录当前搜索进行到的位置，然后遍历所有可能的选项，继续调用dfs函数进行搜索，在搜索完毕后回溯回原来的状态，继续遍历。当搜索完全部位置时，dfs函数返回搜索的值。

小tips

本题由于可以直接覆盖当前位置的选项，可以不用移除最后一个元素，同时把增加一个元素改成修改一个元素。

使用

p = Arrays.asList(new Integer[nums.length]);

可以用n个整数初始化ArrayList，以使得set函数可用。

复杂度

• 时间复杂度: $O(n×n!)$，，其中 n 为序列的长度。
• 空间复杂度: $O(n)$。

Code

class Solution {
    private boolean[] vis;
    private List<List<Integer>> l = new ArrayList<>();
    private List<Integer> p;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        p = Arrays.asList(new Integer[nums.length]);
        vis = new boolean[n];
        dfs(nums, 0);
        return l;
    }

  

    public void dfs(int [] nums, int nowPos) {
        if (nowPos == nums.length) {
            l.add(new ArrayList<>(p));
        }
        for (int i = 0; i < nums.length; i++) {
            if (vis[i] == false) {
                p.set(nowPos, nums[i]);
                vis[i] = true;
                dfs(nums, nowPos + 1);
                vis[i] = false;
            }
        }
    }
}