[LeetCode] Permutations

DFS的做法，在每一位取剩下可以取的值，然后递归到下一位，然后backtracking回来继续考虑其他的可能。
分析时间复杂度的话，我们可以看做在解空间里递归，是一个树状的递归结构，第一层n个分支，然后n - 1个分支......最后两个分支，剩下叶节点。叶节点数量就是全排列的数量，n!。如果是满二叉树的话，我们有n个叶节点，就有n - 1个非叶节点，考虑到这树每层的分叉不一样但是都大于等于2，非叶节点的数量肯定更小。所以对于这道题来说所有节点的数量就是O(n!)。因为是树状搜索，edge的数量也是O(n!)，DFS的时间复杂度就是O(n!)。
时间复杂度O(n!)，空间复杂度O(n)（递归深度），有两种写法。
解法一：

	class Solution {
	public:
	vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> res;
	permute(nums, 0, res);
	return res;
	}
	private:
	void permute(vector<int>& nums, int i, vector<vector<int>>& res)
	{
	if(i == nums.size())
	{
	res.emplace_back(nums);
	return;
	}
	for(int j = i; j < nums.size(); ++j)
	{
	swap(nums[i], nums[j]);
	permute(nums, i + 1, res);
	swap(nums[i], nums[j]);
	}
	}
	};

view raw Permutations_1.cpp hosted with ❤ by GitHub

解法二：

	class Solution {
	public:
	vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> res;
	vector<int> curr;
	vector<bool> marked(nums.size(), false);
	permute(nums, curr, marked, res);
	return res;
	}
	private:
	void permute(vector<int>& nums, vector<int>& curr, vector<bool>& marked, vector<vector<int>>& res)
	{
	if(curr.size() == nums.size())
	{
	res.emplace_back(curr);
	return;
	}
	for(int i = 0; i < nums.size(); ++i)
	{
	if(!marked[i])
	{
	marked[i] = true;
	curr.push_back(nums[i]);
	permute(nums, curr, marked, res);
	curr.pop_back();
	marked[i] = false;
	}
	}
	}
	};

view raw Permutations_2.cpp hosted with ❤ by GitHub