Interview Classic 150 Questions P46 Permutations

---

Timeline

Timeline

2025-11-29

init

---

Problem:

P46 Permutations

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

Permutations backtracking:

#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;
	}
};

Another approach, using swap to exchange the value to the current position, and swap again to restore. This is the fastest.

#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: didn’t think of this swap approach

#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)) // If it already exists
                                continue;
                        // Choose nums[i]
                        curr.push_back(val);
                        uset.insert(val);

                        // Recursion
                        __permute(nums, uset, curr);

                        // Backtrack, remove 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;
        }
};