面试经典150题 P46 全排列

---

时间轴

时间轴

2025-11-29

init

---

题目：

P46 全排列

https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-interview-150

全排列回溯：

#include <vector>
#include <unordered_set>
using std::vector;
using std::unordered_set;

class Solution {
    private:
	void backtrace(vector<vector<int> > &res, vector<int> &track, unordered_set<int> &tset, vector<int> &nums)
	{
		if (track.size() == nums.size()) {
			res.push_back(track);
		}

		for (int num : nums) {
			if (!tset.count(num)) {
				track.push_back(num);
				tset.insert(num);
				backtrace(res, track, tset, nums);
				track.pop_back();
				tset.erase(num);
			}
		}
	}

    public:
	vector<vector<int> > permute(vector<int> &nums)
	{
		vector<vector<int> > res;
		vector<int> track;
		unordered_set<int> tset;
		backtrace(res, track, tset, nums);
        return res;
	}
};

另一种写法，使用 swap 把值交换到当前位置，恢复就再交换一次。这种速度最快。

#include <vector>
using std::vector;

class Solution {
    private:
	void backtrace(vector<vector<int> > &res, vector<int> &nums, int pos)
	{
		int n = nums.size();
		if (pos == n) {
			res.push_back(nums);
			return;
		}

		for (int i = pos; i < n; i++) {
			std::swap(nums[i], nums[pos]);
			backtrace(res, nums, pos + 1);
			std::swap(nums[i], nums[pos]);
		}
	}

    public:
	vector<vector<int> > permute(vector<int> &nums)
	{
		vector<vector<int> > res;

		backtrace(res, nums, 0);
		return res;
	}
};

leetcode hot100 rewrite: 没想到 swap 的这种写法

#include <vector>
#include <unordered_set>
using std::vector;
using std::unordered_set;

class Solution {
    private:
        vector<vector<int> > permutation;
        void __permute(vector<int> &nums, unordered_set<int> &uset, vector<int> &curr)
        {
                if (curr.size() == nums.size()) {
                        permutation.push_back(curr);
                        return;
                }

                for (int val : nums) {
                        if (uset.count(val)) // 如果已经存在
                                continue;
                        // 选择nums[i]
                        curr.push_back(val);
                        uset.insert(val);

                        // 递归
                        __permute(nums, uset, curr);

                        // 回溯，移除nums[i]
                        curr.pop_back();
                        uset.erase(val);
                }
        }

    public:
        vector<vector<int> > permute(vector<int> &nums)
        {
                unordered_set<int> uset;
                vector<int> curr;
                __permute(nums, uset, curr);
                return permutation;
        }
};