analyse

n = (n-k) + (a/b), 其中 a/b == k, k = 1,2,3…,n-1

coding step：

• 1.枚举所有的k，并记录哪些数字被使用
  • 坑1，需要剔除如11,121,222等重复使用数字的k，和如10，102等用到0的k
• 2.对未使用的数排列
  • 坑2，需要排列的数的个数不一，一个used标记数组可能不够，事实上无影响，在排列的过程中，used[i]==true，自动跳过。
• 3.对2中的排列组合，构造a和b，判断是否能组成k
  • 坑3，可能有多种组合，都需要考虑。
  • 受《挑战程序设计竞赛》中“部分和”题的影响，这个坑停了很久，仅仅判断了“对于给定的k，剩下的数能否组成满足条件的a和b，导致少了很多情况”

C++ 代码

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

bool used[10]; // 1-9的状态
int num[10];   // 用于保存排列的顺序 
int res = 0;   // 

void dfs(int target, int s, int pos) { // target == k

    // 1. 全排列1-9未被用到的数字
    // 2. 组合判断能否构成target 
    if(pos == 10 ) { //在排列的叶子节点，组合枚举判断能否构成target
        for(int i = 0 ; i < pos-s; i++) { // 选i个组成a，剩下的组成b
            int a = 0, b = 0;
            for(int j = s; j < s+i; j++) // 选i个数组成a 
                a = a*10 + num[j];
            for(int j = s+i; j < pos; j++) // 剩下的组成b 
                b = b*10 + num[j];
            if (a * target == b ){
//              cout << 100-target << " " << a << " " << b << endl;
                res++;
//              return true;
            }
        }
    }
    for(int i = 1; i < 10; i++) { 
        // 从剩下的10-pos个数中挑一个没被用的数，放在num数组中
        if(!used[i]) {
            // 2.1 备份，此题不用
            // 2.2 改变状态
            used[i] = true;
            num[pos] = i;
            // 2.3 分支
            dfs(target, s, pos+1);
            // 2.4 状态恢复 
            used[i] = false;
            num[pos] = 0;
        }
    }
//  return false;
}

int main(int argc, char** argv) {
    int n;
    cin >> n;

    for(int i = 1; i < n; i ++){
        // 1. 1-9初始化
        for(int j = 0 ; j < 10; j++) used[j] = false;
//      memcpy(used, false, sizeof(used));
        // 2. 枚举整数部分, 1 ~ n-1
        int tmp = i;
        int pos = 1;
        while(tmp != 0) {
            if(used[tmp%10] ) // 去掉整数部分重复的情况 
                break;
            used[tmp%10] = true;
            num[pos++] = tmp%10;
            tmp /= 10;
        }
        // 3. 剔除整数部分包含0的情况 
        if(used[0] || tmp != 0)
            continue;
        // 4. 判断used为false的数能否构成n-i
        dfs(n-i, pos, pos);
    }
    cout << res << endl;
    return 0;
}