【回溯 - 1】46. 全排列

46. 全排列

难度：中等
力扣地址：https://leetcode.cn/problems/permutations/description/

在这里插入图片描述

问题描述

给定一个 不含重复数字 的数组 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]]

示例 3：

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

问题分析

如果这是一道数学题，我们用纸和笔很容易算出来；如果 nums 比较少，我们写多重循环也能算出来。

但现在我们不知道总共多少个数字，现在需要考虑所有可能的全排列结果。

为了方便理解，我们把这道问题修改为排座位的问题。请注意我们此处排座位不考虑任何其他状况，保证 绝对公平，如下图所示：

在这里插入图片描述
现在明确了我们要干的事情，我们需要考虑如何完成这份工作。换句话说，我们应该在何种情况下换座位，保证每位同学坐在某个位置的机会是相等的。

如上图中右边展开的简单树结构所示，总共3位同学的情况下，先确保其中一位同学的座位不变，然后让另外两位同学通过换座，保证公平。

那么现在总共 n 位同学，应该如何保证公平呢？

我们可以考虑使用递归的思想解决这个问题，即，先按住编号为 i 的同学座位不变，其他的人实现公平，然后将编号为 i 的同学换下来，让其他人在 i 以前的位置上轮流坐。

那么应该如何使用代码表示呢？请结合下面的图片进行理解，图片左边是一个示意座次图，右边是代码内容，请结合代码内容换算整个流程。
在这里插入图片描述

代码实现

c++ 的实现：

class Solution {
public:
    void seatSet(vector<vector<int>>& results, vector<int>& nums, int start) {
        if (start == nums.size()) {
            // 已经排好座位，记录一下
            results.push_back(nums);
        } else {
            // 还有排好座位，我们给索引为 [start, nums.size()) 进行排座位
            // 注意公平，每个人坐某个位置的机会是均等的
            for (int i = start; i < nums.size(); i++) {
                // 暂时让 i 同学坐 start 的位置
                swap(nums[i], nums[start]);
                // 剩下的位置[start+1, nums.size()) 还没有排，递归继续排座位
                seatSet(results, nums, start + 1);
                // i 同学在 start 位置上的所有可能已经记录，所以需要把它换回原来位置
                swap(nums[i], nums[start]);
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> results;
        seatSet(results, nums, 0);
        return results;
    }
};

java 的实现：

public class Solution {


    private void seatSet(List<List<Integer>> results, int[] nums, int start) {
        if (start == nums.length) {
            // 已经排好座位，记录一下
            List<Integer> currentPermutation = new ArrayList<>();
            for (int num : nums) {
                currentPermutation.add(num);
            }
            results.add(currentPermutation);
        } else {
            // 还有排好座位，我们给索引为 [start, nums.size()) 进行排座位
            // 注意公平，每个人坐某个位置的机会是均等的
            for (int i = start; i < nums.length; i++) {
                // 暂时让 i 同学坐 start 的位置
                swap(nums, i, start);
                // 剩下的位置[start+1, nums.size()) 还没有排，递归继续排座位
                seatSet(results, nums, start + 1);
                // i 同学在 start 位置上的所有可能已经记录，所以需要把它换回原来位置
                swap(nums, i, start);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        seatSet(results, nums, 0);
        return results;
    }

}

Python 实现

class Solution:
    def permute(self, nums):
        results = []
        self.seat_set(results, nums, 0)
        return results
    
    def seat_set(self, results, nums, start):
        if start == len(nums):
            # 已经排好座位，记录一下
            results.append(nums[:])  # 注意在 Python 中要使用 nums[:] 来复制列表
        else:
            # 还有排好座位，我们给索引为 [start, len(nums)) 进行排座位
            # 注意公平，每个人坐某个位置的机会是均等的
            for i in range(start, len(nums)):
                # 暂时让 i 同学坐 start 的位置
                nums[i], nums[start] = nums[start], nums[i]
                # 剩下的位置[start+1, len(nums)) 还没有排，递归继续排座位
                self.seat_set(results, nums, start + 1)
                # i 同学在 start 位置上的所有可能已经记录，所以需要把它换回原来位置
                nums[i], nums[start] = nums[start], nums[i]