LintCode 返回 570. 寻找丢失的数 II(C++)

描述
中文
English
给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。

n <= 30
数据保证有且仅有唯一解

您在真实的面试中是否遇到过这个题？
样例
样例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

整理大佬的代码。。。。

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
     */
     
     //vector<bool>isSet; 记录哪些数据出现过，哪些数据没出现
     //idx 搜索下标
     
     //将字符串str  从idx到最后中  未出现的数字返回
     int dfs(int idx,vector<bool>isSet,string str,int n)
     {
        if(idx>=str.length())//搜索完所有字符串
        {
            vector<int>leave;//将未出现的数字保存下来
            for(int i=1;i<isSet.size();i++)
            {
                if(!isSet[i])
                    leave.push_back(i);//将未出现的数字记录下来
            }
            if(leave.size()==1)//如果未出现的数字唯一，则为所求结果
                return leave[0];
            else
                return -1;//该种划分失败
        }
        
        if(str[idx]=='0')//该种划分失败
            return -1;
            
        for(int j=1;j<=2;j++)//数字位数 为1位或2位
        {
            
            int num=stoi(str.substr(idx,j));//第一个等待被搜索的数字
            if(num>=1&&num<=n&&!isSet[num])//未出现过
            {
                isSet[num]=true;//更改状态
                int val=dfs(idx+j,isSet,str,n);
                if(val!=-1)
                    return val;
                isSet[num]=false;//回溯
            }
 
        }
        //若上面的划分没有找到唯一解，则划分失败
        return -1;
     }
     
    int findMissing2(int n, string &str) {
        // write your code here
        int res=-1;
        if(n<=0||str.length()<=0)
            return res;
        
        vector<bool>isSet(n+1,false);
        res=dfs(0,isSet,str,n);
        if(res!=-1)
            return res;
        else
            return -1;
        
    }
};