全排列ⅠⅡ（回溯+剪枝）

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>>res;
		DFS(res, temp, nums, 0);
		return res;
	}
	void DFS(vector<vector<int>>&res, vector<int>&temp, vector<int>& nums, int start)
	{

		if (start == nums.size())
		{
			res.push_back(nums);
			return;
		}

		for (int i = start; i < nums.size(); i++)
		{
			swap(nums[start], nums[i]);
			DFS(res, temp, nums, start + 1);//完成后续的全排列
			swap(nums[start], nums[i]);//回溯
		}

	}
};

或者
（更推荐使用这个方法！！！）

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>>res;
		vector<int>temp;
		vector<bool>used(nums.size(), false);
		sort(nums.begin(), nums.end());
		DFS(res, temp, used, nums, 0);
		return res;
	}
	void DFS(vector<vector<int>>& res, vector<int>& temp, vector<bool>&used, vector<int>& nums, int start)
	{


		if (start == nums.size())
		{
			res.push_back(temp);
			return;

		}

		for (int i = 0; i < nums.size(); i++)
		{
			if (used[i] == true)
				continue;

			used[i] = true;
			temp.push_back(nums[i]);
			DFS(res, temp, used, nums, start + 1);//完成后续的全排列
			temp.pop_back();
			used[i] = false;
		}

	}
};

先按升序排列，再进行剪枝。

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>>res;
		vector<int>temp;
		vector<bool>used(nums.size(), false);
		sort(nums.begin(), nums.end());
		DFS(res, temp, used, nums, 0);
		return res;
	}
	void DFS(vector<vector<int>>& res, vector<int>& temp, vector<bool>&used, vector<int>& nums, int start)
	{


		if (start == nums.size())
		{
			res.push_back(temp);
			return;

		}

		for (int i = 0; i < nums.size(); i++)
		{
			if (used[i] == true)
				continue;

			if (i >= 1 && used[i - 1] == false && nums[i] == nums[i - 1])//剪枝
				continue;

			used[i] = true;
			temp.push_back(nums[i]);
			DFS(res, temp, used, nums, start + 1);//完成后续的全排列
			temp.pop_back();
			used[i] = false;
		}

	}
};

最后

以上就是明理火车为你收集整理的全排列ⅠⅡ（回溯+剪枝）的全部内容，希望文章能够帮你解决全排列ⅠⅡ（回溯+剪枝）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。