LeetCode 842. Split Array into Fibonacci Sequence

题解

比较单纯的深搜，有些坑比如数字溢出。
比较一下后两份代码，性能差距明显。

---

Code

bool backtrack(string S, int start, vectorint nums){        
        int n = S.size();
	// If we reached end of string  we have more than 2 elements
	// in our sequence then return true
        if(start = n  nums.size()=3){
            return true;
        }
	// Since '0' in beginning is not allowed therefore if the current char is '0'
	// then we can use it alone only and cannot extend it by adding more chars at the back.
	// Otherwise we make take upto 10 chars (length of INT_MAX)
        int maxSplitSize = (S[start]=='0') ? 1 : 10;
	// Try getting a solution by forming a number with 'i' chars begginning with 'start'
        for(int i=1; i=maxSplitSize  start+i=S.size(); i++){
            long long num = stoll(S.substr(start, i));
            if(num  INT_MAX)
                return false;
            int sz = nums.size();
	// If fibonacci property is not satisfied then we cannot get a solution
            if(sz = 2  nums[sz-1]+nums[sz-2]  num)
                return false;
            if(sz=1 || nums[sz-1]+nums[sz-2]==num){
                nums.push_back(num);
                if(backtrack(S, start+i, nums))
                    return true;
                nums.pop_back();                
            }
        }
        return false;
    }
    
    vectorint splitIntoFibonacci(string S) {
        vectorint nums;
	// Backtrack from 0th char
        backtrack(S, 0, nums);
        return nums;
    }

拙作留念

void dfs(string s,int index,vectorint cot,vectorint res){
        if(cot.size()=3){
            for(int i=0;icot.size()-2;i++){
                if(cot[i]+cot[i+1]!=cot[i+2])
                    return;
            }
        }
        if(index=s.size()cot.size()=3){
            res=cot;
            return;
        }
        
         for(int k=1;k+index=s.size()k=10;k++){
                long long num=stoll(s.substr(index,k));
                if(num=INT_MAX) break;
                cot.push_back(num);
                dfs(s,index+k,cot,res);
                cot.pop_back();
                if(num==0)   break;
            }
    }
    vectorint splitIntoFibonacci(string S) {
        vectorint cot, res;
        dfs(S,0,cot,res);
        return res;
    }