Keywords

backtrack 回溯算法

图解

举例： [1, 2, 3] ，顺着叶子节点和删除的节点就可以还原成全排列。

从上面图可以看出来，叶子节点加上回溯路径上被移除的节点就是结果的一项，从左到右依次是：

  • [3,R:2,R:1] -> [3,2,1]
  • [2,R:3,R:1] -> [2,3,1]
  • …
class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> res;
		vector<int> track;
		backtrack(res, track, nums);
		return res;
	}

	void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) {
		if (track.size() == nums.size()) {
			res.push_back(track);
			return;
		}

		for (int i = 0; i < nums.size(); i++) {
			if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) {
				continue;
			}

			track.push_back(nums[i]);
			visited[nums[i]] = true;

			// go into next level
			backtrack(res, track, nums);

			visited[nums[i]] = false;
			track.pop_back();
		}
	}
private:
	map<int, bool> visited;
};

根据视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo

得出以下解法：

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> res;
		int n, i;
		vector<vector<int>> perms;

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

		for (i = 0; i < nums.size(); i++) {
			n = nums.back();
			nums.pop_back();
			perms = permute(nums);
			for (auto perm : perms) {
				perm.push_back(n);
				res.push_back(perm);
			}
			nums.insert(nums.begin(), n);
		}

		return res;
	}
};