【原】晚上，突然接到领导电话，问我愿不愿意到越南上班，工资35000元，合同期限5年，双倍年终奖。

数据结构和算法 2024-04-15 发布于上海

展开全文

一网友说，在一天晚上，突然接到领导的电话，问愿不愿意到越南icon上班，工资35000元，合同期限5年，双倍年终奖，这个薪水确实令他心动，但是又有点犹豫。

如果是正规的大公司并且工资涨幅比较高的话可以考虑去，毕竟越南相对还是比较安全的，而其他网友有建议不要去的，担心会被卖到缅甸，也有建议去的，毕竟是个机会。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第46题：全排列。

问题描述

来源：LeetCode第46题

难度：中等

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

问题分析

这是一道经典的回溯算法问题，之前在讲什么叫回溯算法，一看就会，一写就废的时候，也提到过使用回溯算法来解决。

假设数组长度是n，每次只能从数组中取出一个元素，我们可以把它看作是一颗n叉树的dfs遍历，使用递归，当往下走的时候选择当前元素，往回走的时候撤销选择，可以看下动画演示。

JAVA：

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

private void dfs(List<List<Integer>> ans, List<Integer> path, int[] nums, boolean[] visited) {
    // 终止条件，如果数字都被使用完了，说明找到了一个排列
    if (path.size() == nums.length) {
        // 因为list是引用传递，这里必须要重新new一个
        ans.add(new ArrayList<>(path));
        return;
    }
    // 可以把它看做是遍历n叉树每个节点的子节点
    for (int i = 0; i < nums.length; i++) {
        // 因为不能有重复的，所以有重复的就跳过
        if (visited[i])
            continue;
        // 选择当前元素
        visited[i] = true;
        path.add(nums[i]);
        //递归（可以把它看做遍历子节点的子节点）
        dfs(ans, path, nums, visited);
        // 撤销选择，把最后一次添加的元素给移除
        visited[i] = false;
        path.remove(path.size() - 1);
    }
}

C++：

public:
    vector<vector<int>> permute(vector<int> &nums) {
        vector<bool> visited(nums.size(), false);
        dfs(nums, visited);
        return ans;
    }

private:
    vector<vector<int>> ans;
    vector<int> path;

    void dfs(vector<int> &nums, vector<bool> &visited) {
        // 终止条件，如果数字都被使用完了，说明找到了一个排列
        if (path.size() == nums.size()) {
            ans.emplace_back(path);
            return;
        }
        // 可以把它看做是遍历n叉树每个节点的子节点
        for (int i = 0; i < nums.size(); i++) {
            // 因为不能有重复的，所以有重复的就跳过
            if (visited[i])
                continue;
            // 选择当前元素
            visited[i] = true;
            path.emplace_back(nums[i]);
            //递归（可以把它看做遍历子节点的子节点）
            dfs(nums, visited);
            // 撤销选择，把最后一次添加的元素给移除
            visited[i] = false;
            path.pop_back();
        }
    }

C：

void dfs(int **ans, int *returnSize, int *path, int index, int *nums, int numsSize, int *visited);

int **permute(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    int **ans = malloc(720 * sizeof(int *));
    *returnColumnSizes = malloc(720 * sizeof(int));
    int *path = malloc(6 * sizeof(int));
    int *visited = calloc(1, sizeof(int));
    *returnSize = 0;
    dfs(ans, returnSize, path, 0, nums, numsSize, visited);
    for (int i = 0; i < *returnSize; ++i)
        (*returnColumnSizes)[i] = numsSize;
    return ans;
}

void dfs(int **ans, int *returnSize, int *path, int index, int *nums, int numsSize, int *visited) {
    // 终止条件，如果数字都被使用完了，说明找到了一个排列
    if (index == numsSize) {
        ans[(*returnSize)] = malloc(index * sizeof(int));
        memcpy(ans[(*returnSize)++], path, index * sizeof(int));
        return;
    }
    // 可以把它看做是遍历n叉树每个节点的子节点
    for (int i = 0; i < numsSize; i++) {
        // 因为不能有重复的，所以有重复的就跳过
        if (((*visited) & (1 << i)) != 0)
            continue;
        // 选择当前元素
        (*visited) |= 1 << i;
        path[index++] = nums[i];
        //递归（可以把它看做遍历子节点的子节点）
        dfs(ans, returnSize, path, index, nums, numsSize, visited);
        // 撤销选择，把最后一次添加的元素给移除
        (*visited) &= ~(1 << i);
        index--;
    }
}

Python：

def permute(self, nums: List[int]) -> List[List[int]]:
    def dfs():
        # 终止条件，如果数字都被使用完了，说明找到了一个排列
        if len(path) == len(nums):
            ans.append(path[:])
            return

        # 可以把它看做是遍历n叉树每个节点的子节点
        for i in range(0, len(nums)):
            # 因为不能有重复的，所以有重复的就跳过
            if visited[i]:
                continue
            # 选择当前元素
            visited[i] = True
            path.append(nums[i])
            # 递归（可以把它看做遍历子节点的子节点）
            dfs()
            # 撤销选择，把最后一次添加的元素给移除
            visited[i] = False
            path.pop()

    ans = []
    path = []
    visited = [False for _ in range(len(nums))]
    dfs()
    return ans