面试经典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;
	}
};