[刷题]递归回溯专题

1. [剑指Offer 面试题17] 打印从1到最大的n位数

• 题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3， 打印出1,2，…，999。
• 解法：
  • 全排列解，这里主要用这个方式，有需要在输出时，对高位0进行截断。
  • 大数加法解
• 代码：

  class Overview17
  {
  public:
  	Overview17(){}
  	~Overview17(){}
  
  	void PrintAllNumber(int n){
  		vector<int> curr; // 递归当前数字
  		vector<vector<int>> res; //全部数字列表
  
  		dfs(res, 0, n, curr);
  		
          // 打印数字
  		for (auto item : res){
  			for (auto it : item)
  			{
  				cout << it;
  			}
  			cout << endl;
  		}
  
  	}
  
  	void dfs(vector<vector<int>> & res, int depth, int n, vector<int> curr){
  		if (depth >= n){
  			res.emplace_back(curr);
  			return;
  		}
  			
  		for (int i = 0; i < 10; i++){
  			curr.emplace_back(i);
  			dfs(res, depth + 1, n, curr);
  			curr.pop_back();
  		}
  	}
  };
  
  int main()
  {
  	Overview17 ocs;
  	ocs.PrintAllNumber(2);
  	return 0;
  }

2. [Leetcode 46] 全排列

• 解法：递归，注意去重
• 代码：

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		if (nums.size() == 0) return{};
		vector<vector<int>> res;
		vector<int> curr_vec;
		vector<bool> used;
		for (int i = 0; i < nums.size(); i++)
		{
			used.push_back(false);
		}
		dfs(res, nums, 0, curr_vec, used);
		return res;
	}

	void dfs(vector<vector<int>>& res, vector<int>& nums, int depth, vector<int> curr_vec, vector<bool> used)
	{

		if (depth >= nums.size())
		{
			res.emplace_back(curr_vec);
			return;
		}

		for (int i = 0; i < nums.size(); i++)
		{
			if (used[i]) continue;
			used[i] = true;
			curr_vec.emplace_back(nums[i]);
			dfs(res, nums, depth + 1, curr_vec, used);
			curr_vec.pop_back();
			used[i] = false;
		}
	}
};

3. [Leetcode 47] 全排列 II

• 解法: 递归，有可重复数字，不要递归重了。对数列进行排序，让相同的数字连在一起，如果当前位已经使用过，或者该位的前一位与该位相同并且前一位没有被使用过，这时两个排列会相同，因而略过。
• 代码:

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		if (nums.size() <= 0) return{};

		sort(nums.begin(), nums.end());
		
		vector<vector<int>> res;
		vector<bool> used;
		vector<int> curr;
		
		for (auto item : nums)
		{
			used.push_back(false);
		}

		dfs(res, nums, curr, used, 0);
		return res;
	}

	void dfs(vector<vector<int>>& res, vector<int>& nums, vector<int> curr, vector<bool> used, int depth)
	{
		if (depth >= nums.size())
		{
			res.emplace_back(curr);
			return;
		}

		for (int i = 0; i < nums.size(); i++)
		{
			if (used[i]) continue; 
			if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;

			used[i] = true;
			curr.emplace_back(nums[i]);
			dfs(res, nums, curr, used, depth + 1);
			curr.pop_back();
			used[i] = false;
		}
	}
};