C++ dfs solution


  • 0
    Q
    class Solution {
    public:
        int triangleNumber(vector<int>& nums) {
            if(nums.size() < 3)
                return 0;
            sort(nums.begin(),nums.end());
            
            int res = 0;
            vector<int> t;
            dfs(nums,0,t,res);
            return res;
        }
        
        void dfs(vector<int> nums, int start, vector<int> t, int& res){
            if(t.size() > 3)
                return;
            if(t.size() == 3){
                res++;
                return;
            }
            for(int i=start;i<nums.size();i++){
                if(t.size() < 2){
                    t.push_back(nums[i]);
                    dfs(nums,i+1,t,res);
                    t.pop_back();
                }
                if(t.size() == 2){
                    //cout<<"line 28 "<<res<<" "<<t[0]+t[1]<<" "<<i<<endl;
                    int l = find_lower(nums,i,t[0]+t[1]);
                    res += l;
                    //cout<<"line 31 "<<res<<endl;
                    break;
                }
            }
            return;
        }
        
        int find_lower(vector<int> vec, int start, int target){
            int low = start, high = vec.size()-1;
            int mid;
            while(low <= high){
                mid = (low+high)/2;
                if(vec[mid]>=target)
                    high = mid-1;
                else
                    low = mid+1;
            }
            if(low == vec.size() || vec[low] >=target)
                low--;
            
            return low-start+1; 
        }
    };
    

Log in to reply
 

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