# LeetCode Valid Triangle Number

LeetCode Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

```Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
```

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

```class Solution {
private:
void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
++ans;
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
int ans = 0;
vector<int> cand;
sort(nums.begin(), nums.end());
dfs(ans, nums, cand, 0);
return ans;
}
};
```

```class Solution {
private:
void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
ans += count[a] * count[b] * count; // 三边各异
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, count, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
vector<int> mii(1001, 0);
for (const auto& i : nums)++mii[i]; // hash
vector<int> distinct;
for (int i = 1; i < 1001; ++i) {
if (mii[i] > 0)distinct.push_back(i);
}

int ans = 0;
vector<int> cand;
dfs(ans, mii, distinct, cand, 0); // 三边互不相同

int n = distinct.size();
for (int i = 0; i < n; ++i) {
if (mii[distinct[i]] >= 3) { // 三边相同
int &d = mii[distinct[i]];
ans += (d*(d - 1)*(d - 2)) / 6;
}
for (int j = i + 1; j < n; ++j) {
if (mii[distinct[i]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[i], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[a] * (mii[a] - 1) / 2)*mii;
}
}
if (mii[distinct[j]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[j], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[b] * (mii[b] - 1) / 2)*mii[a];
}
}
}
}

return ans;
}
};
```