C++ dfs solution

• ``````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;
}
};
``````

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