Can someone take a look at my solution and explain why it is incorrect?


  • 0
    A

    Ignore the "vector<int> cache". That was for debugging purposes only.

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            sort(A.begin(),A.end());
            int count = 0;
            vector<int> cache;
            helper(A,0,-1,-1,count,1,cache);
            return count;
        }
        void helper(const vector<int>& A, const int index, const int last, const int diff, int& count, const int depth, vector<int>& cache){
            if( depth > A.size() ){
                return;
            }
            for( int i = index; i < A.size(); ++i ){
                //picking first number
                if( depth == 1 ){
                    cache.push_back(A[i]);
                    helper(A,i+1,A[i],-1,count,depth+1,cache);
                    cache.pop_back();
                    //avoid duplicates
                    while( i+1 < A.size() && A[i+1] == A[i] ){
                        ++i;
                    }
                    continue;
                }
                //establishing difference
                if( depth == 2 ){
                    cache.push_back(A[i]);
                    helper(A,i+1,A[i],A[i]-last,count,depth+1,cache);
                    cache.pop_back();
                    //avoid duplicates
                    while( i+1 < A.size() && A[i+1] == A[i] ){
                        ++i;
                    }
                    continue;
                }
                //depth >=3
                //check diff
                if( A[i] - last == diff ){
                    count++;
                    cache.push_back(A[i]);
                    helper(A,i+1,A[i],diff,count,depth+1,cache);
                    cache.pop_back();
                    //avoid duplicates
                    while( i+1 < A.size() && A[i+1] == A[i] ){
                        ++i;
                    }
                    //return;
                }
                else if( (A[i] - last) > diff ){
                    break;
                }
            }
        }
    };

  • 0
    D

    I'm not sure if you are still working on this problem. But I see that your code fails for cases like A = {1,2,3,4,3}. It considers the first {1,2,3} subsequence but not the second one.


Log in to reply
 

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