LeetCode 46. 全排列(C++)

题目地址：力扣 题目难度：Medium

涉及知识点：广度优先遍历、回溯、树形结构

---

分析：这道题要输出所有的数的全排列，首先我们可以想到的是依次选数，假设数组的大小为3，那么第一个位置就有3种选择，三种选择下面对应的第二个位置又分别有两种选择，第三个位置没有选择。因此我们可以构造一颗树来求解这个问题。下面以三个数的数组[1,2,3]为例构建一棵树。

---

解法1：广度优先遍历

思路：用队列记录下每一层的所有情况，并在下层遍历的时候，根据上层的每一项分别添加上每一种可能加入队列，直到所有数都被选择进队列。

class Solution {
public:
    vector> permute(vector& nums) {
        // sz记录数组大小,que用于层序遍历，res用于返回
        int sz = nums.size();
        queue> que;
        vector> res;
        // 遍历数组中每一个数，将其加入队列中（树的第一层）
        for (int i = 0; i < sz; ++i)
        {   
            que.emplace(vector {nums[i]});
        }
        // 遍历选择每个位置的元素，由于数组中第0的位置元素已经选完了，这里从第1个位置开始选
        for(int i = 1; i < sz; ++i)
        {
            // 记录当前队列的大小，表示本层包含多少元素
            int que_sz = que.size();
            // 遍历本层所有的节点
            while (que_sz != 0) {
                // 遍历一遍数组，看看哪些元素是可以选的
                for (int j = 0; j < sz; ++j)
                {
                    // 拿出队列头节点
                    vector tmp = que.front();
                    // 若队列头结点的数组中不包括当前的元素，那么就选择它加入数组，并把数组加入队列
                    if (find(tmp.begin(), tmp.end(), nums[j]) == tmp.end()) {
                        tmp.push_back(nums[j]);
                        que.push(tmp);
                    }
                }
                // 所有可能性都加完之后才出队，并把记录的变量减1
                que.pop();
                --que_sz;
            }
        }
        // 记录下最终队列的大小，此时已经是树的最后一层
        int que_sz = que.size();
        // 将队列中的元素一个个放进res中并返回
        for (int i = 0; i < que_sz; ++i) 
        {  
            res.push_back(que.front());
            que.pop();
        }
        return res;
    }
};

---

解法2：深度优先遍历（回溯）

思路：由于我们发现在确定某个元素的时候存在多个值可供选择，而我们采用深度优先遍历的话会找到叶子结点，也就是确定最终的某个排列结果。因此回溯要求的就是我们可以回到上一步的状态，看看是否有其他的选择，如果有的话就输出下一种选择。因此我们可以用一张表来记录哪些元素当前是已经选择了的，在回退的时候修改这张表就可以了。

class Solution {
public:
    // 接受四个参数，均为引用类型避免复制的开销
    void backTrack(vector &nums, vector &selected, 
                   vector &curSelect, vector> &res)
    {
        // 若当前选择数的大小不等于全部数的大小
        if (curSelect.size() != nums.size()) {
            // 遍历数组中每个元素
            for (int i = 0; i < nums.size(); ++i) 
            {
                // 若未被选择
                if (!selected[i]) {
                    // 选择它，并把其标志位置为true
                    curSelect.push_back(nums[i]);
                    selected[i] = true;
                    // 继续递归寻找下一个位置的元素
                    backTrack(nums, selected, curSelect, res);
                    // 出递归，说明已经找完了一轮，那么将该数重置为未选择，并继续遍历下一个数
                    selected[i] = false;
                    curSelect.pop_back();
                }
            }
        }
        //  若当前选择数的大小等于全部数的大小,说明已经全部选完了，可以加入结果了
        else {
            res.push_back(curSelect);
        }
    }

    vector> permute(vector& nums) {
        // sz记录数组大小, res用于返回, selected用于保存选择的状态，cur保存当前已选择的元素
        int sz = nums.size();
        vector> res;
        // 初始的标志位全部默认为false
        vector selected(sz);
        vector cur;

        backTrack(nums, selected, cur, res);
        return res;
    }
};

Accepted

• 26/26 cases passed (4 ms)
• Your runtime beats 61.21 % of cpp submissions
• Your memory usage beats 71.42 % of cpp submissions (7.5 MB)