描述
给一个由 1 -n的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
n < 100
数据保证有且仅有唯一解

在线评测地址：领扣题库官网

样例1
输入: n = 20 和 str = 19201234567891011121314151618
输出: 17
解释:
19'20'1'2'3'4'5'6'7'8'9'10'11'12'13'14'15'16'18

样例2
输入: n = 6 和 str = 56412
输出: 3
解释:
5'6'4'1'2

题解
算法：深度优先搜索

• dfs(now,step,n,len)表示当前的状态为考虑到了第now个字符（第now个字符还没使用），拼凑出来了step个数 一共需要拼出n-1个数，len是整个字符串的长度
• 枚举下次用一个字母还是两个字母来组成新的一个数字，判断组成的数字是不是在1到n之间，判断组成的数字有没有用过，判断组成的数字有没有前导0
• 判断结束后，递归搜索下一层
• 当now==len 并且 step==n-1时看看哪个数字没有用过就找到了最终答案
• 剪枝

剩下的字符每个字符都是一个数字 也凑不到n-1个数字
if(step+len-now<n-1) {

                return 0;

}
剩下的字符每两个字符构成一个数字，构成的数字也比n-1个要多
if(step+(len-now)/2>n-1){

                return 0;

}

复杂度

• 时间复杂度

O(C(n,len))O(C(n,len))
C表示组合数，n是多少个数字，len是字符串长度，但因为有很多剪枝，状态量要远远低于这个C(n,len)

• 空间复杂度

多开辟了标记数字有没有用过的数组visO(N)O(N)N是给定的n
代码

class Solution {
  public:
    /**
     * @param n: An integer
     * @param str: a string with number from 1-n in random order and miss one number
     * @return: An integer
     */

    int vis[50];
    char s[100];
    int dfs(int now, int step, int n, int len) {

        //找到解了
        //用了len个字符，拼出来n-1个数字
        if(step == n - 1 && now == len) {
            for(int i = 1; i <= n; i++) {
                if(vis[i] == 0) {
                    return i;
                }
            }
            return 0;
        }
        //剩下的字符每个字符都是一个数字 也凑不到n-1个数字
        if(step + len - now < n - 1) {

            return 0;
        }
        //剩下的字符每两个字符构成一个数字，构成的数字也比n-1个要多
        if(step + (len - now) / 2 > n - 1) {

            return 0;
        }
        //下个数字是多少
        int tmp = 0;
        for(int i = 0; i <= 1; i++) {

            tmp = tmp * 10 + s[now + i] - '0';
            //不能有前导0
            if(tmp == 0)break;
            // 判断tmp在不在1到n范围内，判断有没有使用超过len个字符 判断tmp之前有没有用过
            if(vis[tmp] == 0 && tmp <= n && tmp >= 1 && now + i < len) {
                vis[tmp] = 1;
                int ans = dfs(now + 1 + i, step + 1, n, len);
                vis[tmp] = 0;
                //ans非0 表示找到了解
                if(ans) {
                    return ans;
                }
            }
        }
        return 0;
    }
    int findMissing2(int n, string &str) {
        //转成char数组
        strcpy(s, str.c_str());
        //初始化
        for(int i = 1; i <= n; i++) {
            vis[i] = 0;
        }
        int len = str.size();
        int ans = dfs(0, 0, n, len);
        return ans;
    }
};

更多题解参考：https://www.jiuzhang.com/solution/find-the-missing-number-ii/?utm_source=sc-zhihuzl-sy