Dfs深搜可解，但题目有坑的地方。
题目链接：·【蓝桥】·带分数

问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字19分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码19不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6

算法思想
Dfs对1~9进行全排列，将每组数分成三段（两重循环标记）， 满足a+b/c==m && b%c==0就记作一组解。

• 解题思路很容易想到，具体实现时有坑的地方要注意。

C++的next_permutation实现全排列

• 将每组结果分段的过程涉及到子串查找；

***值得注意的地方在于：当程序需要过多查找子串的操作，不要用string（如下面代码中注释掉的内容），使用const char *效率最高。
———————————————完整代码————————————————

#include <iostream>
#include <string> 
#include <sstream>
#include <algorithm>
using namespace std;

int sum = 0, m;
int toInt(const char *str, int pos, int len){
	int ans = 0, t = 1;
	for(int i = pos+len-1; i >= pos; i--){
		ans += (str[i]-'0')*t;
		t *= 10;		
	}
	// for(int i = 0; i < len; ++i){
	// 	ans = 10*ans+(str[pos++]-'0');
	// }
	return ans;
}
int main(){
	cin >> m;
	string str = "123456789";
	do{
		const char *s = str.c_str();
		for(int i = 1; i <= 7; ++i){
//			string a = str.substr(0, i);
//			int a1 = toInt(a);
			int a1 = toInt(s, 0, i);//第一个数a
			if(a1 >= m)
				break;
			for(int j = 1; j <= 9-i-1; ++j){
//				string b = str.substr(i, j);
//				string c = str.substr(i+j);
//				int b1 = toInt(b);
//				int c1 = toInt(c);
				int b1 = toInt(s, i, j);//第二个数b
				int c1 = toInt(s, i+j, 9-i-j);//第三个数c
				if(b1%c1==0 && (a1+b1/c1)==m){
					sum++;
				}
			}
		}
	}while(next_permutation(str.begin(), str.end()));
	cout << sum << endl;
	return 0;
}

手写Dfs实现全排列

• 手写一个没有多难嘛，但同时要注意上面提到的const char *问题
• 当要将字符串与数值拼接，C++就有点讨厌了，只会用 stringstream
  stringstream ss;
ss << str << i;

———————————————完整代码————————————————

#include <iostream>
#include <string> 
#include <sstream>
using namespace std;

int visit[10];
int sum = 0, m;
string str;
int toInt(const char *str, int pos, int len){
	int ans = 0, t = 1;
	for(int i = pos+len-1; i >= pos; i--){
		ans += (str[i]-'0')*t;
		t *= 10;		
	}
	return ans;
}
void Dfs(string str, int step){
	if(step >= 9){
		const char *s = str.c_str();
		for(int i = 1; i <= 7; ++i){
			int a1 = toInt(s, 0, i);
			if(a1 >= m)
				continue;
			for(int j = 1; j <= 9-i-1; ++j){
				int b1 = toInt(s, i, j);
				int c1 = toInt(s, i+j, 9-i-j);
				if(b1%c1==0 && (a1+b1/c1)==m){
					sum++;
				}
			}
		}
		return;
	}
	for(int i = 1; i <= 9; ++i){
		if(visit[i] == 0){
			visit[i] = 1;
			stringstream ss;
			ss << str << i; //实现str+i
			Dfs(ss.str(), step+1);
			visit[i] = 0;
		}
	}
}
int main(){
	cin >> m;
	Dfs(str, 0);
	cout << sum << endl;
	return 0;
}