長さが \(x,y,z\) の \(3\) 本の棒を使って三角形を作ることができるための必要十分条件は「\(x+y>z\) かつ \(y+z>x\) かつ \(z+x>y\)」が成り立つことです。

「1番目の棒をどの棒と組み合わせて三角形を作るかを決め、残った棒たちに関して再帰的に問題を解く」とすることでこの問題を解くことができます。詳しくは実装例をご覧ください。計算量は実装方法にもよりますが \(O(\frac{N(3N)!}{6^NN!})\) 程度となります。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

bool f(int x,int y,int z){
  return x+y>z && y+z>x && z+x>y;
}

int dfs(vector<int>a){
  int n=a.size();
  if(n==0)return 1;
  int ans=0;
  for(int j=1;j<n;j++){
    for(int k=j+1;k<n;k++){
      if(f(a[0],a[j],a[k])){
        vector<int>b(a.begin(),a.end());
        b.erase(b.begin()+k);
        b.erase(b.begin()+j);
        b.erase(b.begin());
        ans+=dfs(b);
      }
    }
  }
  return ans;
}

int main(){
  int n;
  cin >> n;
  vector<int>a(3*n);
  for(int i=0;i<3*n;i++)cin >> a[i];
  cout << dfs(a) << endl;
}

実装例(Python)

def f(x,y,z):
  return x+y>z and y+z>x and z+x>y

def dfs(A):
  n=len(A)
  if n==0: return 1
  ans=0
  for j in range(1,n):
    for k in range(j+1,n):
      if f(A[0],A[j],A[k]):
        ans+=dfs(A[1:j]+A[j+1:k]+A[k+1:])
  return ans

input()
A=list(map(int,input().split()))
print(dfs(A))