问题描述：
1,2，...，9这九个数字组成一个分数，其值恰好为1/3。
求解思路：
=1/3，其中
和
分别有1,2，...，9这九个数字来构成，那么可以
是由4个数字构成，
是由5个数字构成的，用int a[9]来记录
,
各数字位的值，bool b[10]来记录1,2，...，9是否被使用。这里可以使用剪枝来加速搜索速度，分子最小为a[0]*1000，最大为(a[0]+1)*1000，分母最小为a[4]*10000，最大为(a[4]+1)*10000。可以过滤掉那些“a[0]*1000/(a[4]+1)*10000 > 1/3”的值。
C++代码：
#include<iostream>
using namespace std;
int a[9];
bool b[10];
void dfs(int cur) {
if (cur == 9) {
int x = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
int y = a[4] * 10000 + a[5] * 1000 + a[6] * 100 + a[7] * 10 + a[8];
if (3 * x == y)
cout << x << "/" << y << "= 1/3" << endl;
}
else {
for (int i = 1; i < 10; i++) {
if (cur >= 4) {
if (3 * a[0] > 10 * (a[4] + 1))
continue;
}
if (!b[i]) {
a[cur] = i;
b[i] = 1;
dfs(cur + 1);
b[i] = 0;
}
}
}
}
int main() {
dfs(0);
return 0;
}
