[LeetCode]Beautiful Arrangement

想过用DP的方法从subproblem开始推，但是找不到递推公式，所以还是采用permutation + 剪枝的方法，把不符合条件的permutation提早cut掉来节省时间。参考Permutations的写法，时间复杂度O(k)，k为结果数，空间复杂度O(n)（递归深度），代码如下：

解法一：

	class Solution {
	public:
	int countArrangement(int N) {
	vector<int> nums;
	for(int i = 1; i <= N; ++i)
	nums.push_back(i);
	int count = 0;
	permute(nums, 0, count);
	return count;
	}
	private:
	void permute(vector<int>& nums, int start, int& count)
	{
	if(start == nums.size())
	{
	++count;
	return;
	}
	for(int i = start; i < nums.size(); ++i)
	{
	//we only need to consider if curr slot is valid
	//we will consider the other slot when we reach it
	if(nums[i] % (start + 1) == 0 || (start + 1) % nums[i] == 0)
	{
	swap(nums[start], nums[i]);
	permute(nums, start + 1, count);
	swap(nums[start], nums[i]);
	}
	}
	}
	};

view raw Beautiful Arrangement_1.cpp hosted with ❤ by GitHub

解法二：

	class Solution {
	public:
	int countArrangement(int N) {
	int count = 0;
	vector<bool> marked(N, false);
	backtrack(marked, 1, count);
	return count;
	}
	private:
	void backtrack(vector<bool>& marked, int idx, int& count)
	{
	if(idx == marked.size() + 1)
	{
	++count;
	return;
	}
	for(int i = 1; i <= marked.size(); ++i)
	{
	if(!marked[i - 1] && (idx % i == 0 || i % idx == 0))
	{
	marked[i - 1] = true;
	backtrack(marked, idx + 1, count);
	marked[i - 1] = false;
	}
	}
	}
	};

view raw Beautiful Arrangement_2.cpp hosted with ❤ by GitHub