「POJ2362」Square

2015年1月22日2,3950

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick – an integer between 1 and 10,000.

Output

For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.

Sample Input

Sample Output

题解

搜索+剪枝

倒序排序缩小搜索树

当前长度加上最小长度大于边长,返回

某长度不能完成某个子问题,和它一样长的也不能完成。

其实不加剪枝似乎也行

 

avatar
  Subscribe  
提醒