46_全排列.md

全排列

46. 全排列 - 力扣（LeetCode） (leetcode-cn.com)

分析

递归枚举 (dfs)

我们针对全排列后的新数组的每一位进行枚举。如果数组长度为n，枚举的位数为i，那么当前位可以有 n - i 种选择。

于是，时间复杂度为O(n * n!)。

class Solution {
    List<List<Integer>> ans;
    boolean[] mark;
    int n;

    public List<List<Integer>> permute(int[] nums) {
        n = nums.length;
        ans = new ArrayList<>();
        mark = new boolean[n];
        dfs(nums, 0, new Integer[n]);
        return ans;
    }

    private void dfs(int[] nums, int idx, Integer[] list) {
        if (idx == n) {
            List<Integer> t = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                t.add(list[i]);
            }
            ans.add(t);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (mark[i]) continue;
            mark[i] = true;
            list[idx] = nums[i];
            run(nums, idx + 1, list);
            mark[i] = false;
        }
    }
}