求三角形子集的个数

角形子集的个数"/>

求三角形子集的个数

求三角形子集的个数

已知有n个值，求他们能组成多少个三角形

1. 给定n条边，求能组成三角形的子集个数，首先将给定数组排序，定义三个指针。
2. 分别枚举三角形的三条边，若前两个指针能保证指向的元素大于第三个指针指向的元素。
3. 则表明后两个指针所包围的元素一定能组成三角形，根据非空集合公式2^n - 1可求集合个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {ll ans = 0;   // 求和sum int n,a[100],k;cin >> n;for(int i=1;i<=n;i++) cin >> a[i];sort(a+1,a+n+1);for(int i=1;i<=n-2;i++){for(int j=i+2;j<=n;j++){for(k=i+1;k<=j;k++){if(a[k]+a[i]>a[j])break;}ans += pow(2,j-k)-1;}}cout << ans << endl;return 0;
}