【深度优先搜索】最大乘积：排列

把 1 ~ 99 这 9 个数字分成两组，中间插入乘号， 有的时候，它们的乘积也只包含 1 ~ 9 这 9 个数字，而且每个数字只出现1次。

比如：

984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

注意，需要输出的是一个整数，表示那个最大的积，只输出乘积，不要输出整个算式。

dfs(cnt,mult):cnt选择次数，mult记录当前选择的数组成的乘积。

一共要做9次选择，每次做选择时只能从1~9中选，且同一路径上的数要去重。每次选择一个数后，更新mult的值，即第一操作数。

在第一操作数固定的情况下，如果要使乘积最大，那么第二操作数必须最大，所以第二操作数也可以求出，即在所有未被标记的数的组合情况的最大值。（逆序排列即可）

在一开始求出第二操作数，并判断它们的乘积是否合法，如果合法更新最大值。

注意：在每一次做选择之后都要求出第二操作数，并判断乘积是否合法。所以，这些操作在开头写，且不能用return语句返回掉，这类似求所有一组数的所有组合情况。

代码：

#include 
#include
#include
using namespace std;
vectorpath;
bool vis[11];
bool vis1[11];
long long res = 0;
int f() {
    int n = 0;
    for (int i = 9; i >= 1; i--) {
        if (vis[i] == false) {
            n = n * 10 + i;
        }
    }
    return n;
}
bool check(long long n) {
    int m = n;
    while (m) {
        if (m % 10 == 0)return false;
        if (vis1[m % 10] == true)return false;
        vis1[m % 10] = true;
        m /= 10;
    }
    for (int i = 1; i <= 9; i++) {
        if (vis1[i] == false)return false;
    }
    return true;
}
void dfs(int index, int mult) {
  //不能使用对称性
    if (index > 9)return;
    int other = f();
    long long n = mult * other;
    memset(vis1, 0, sizeof(vis1));
    if (check(n)) {
        res = max(res, n);
    }
    for (int i = 1; i <= 9; i++) {
        if (vis[i] == true)continue;
        vis[i] = true;
        dfs(index + 1, mult * 10 + i);
        vis[i] = false;
    }

}
int main()
{
    dfs(0, 0);
    cout << res;
    // 请在此输入您的代码
    return 0;
}