C# back tracking solution


  • 0
    D

    Not the neatest possible code, but classic BT implementaion.

    public bool IsAdditiveNumber(string num) {
        List<long> soFar = new List<long>();
        return func(num, 0, soFar);
    }
    
    private bool func(string num, int index, List<long> soFar){
        if(index == num.Length && soFar.Count > 2) return true;
        for(int i=index; i < num.Length; i++)
        {
            if(num[index] == '0' && i > index) return false;
            long n;
            if(!Int64.TryParse(num.Substring(index, i-index+1), out n)){
                return false;
            }
            if(soFar.Count >= 2 && soFar[soFar.Count-1] + soFar[soFar.Count-2] < n) return false;
            
            if(soFar.Count < 2 || soFar[soFar.Count-1] + soFar[soFar.Count-2] == n){
                soFar.Add(n);
                if(func(num, i+1, soFar)) return true;
                soFar.RemoveAt(soFar.Count-1);
            }
        }
        
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.