2013
11-11

# Square

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

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.

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

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5


yes
no
yes


import java.io.*;
import java.util.*;

public class Main {

//璁板��板�����垮害��
int totalNum;
//璁板���釜�板�������缁��
int[] numArr;
//璁板�姣�釜灏��妫�����浣跨�杩��
boolean[] used;

public static void main(String args[]) throws Exception {
Main m=new Main();
m.begin();
}

private void begin() throws Exception {
Scanner cin = new Scanner(System.in);
int totalLine = cin.nextInt();
for(int i=0; i< totalLine; i++){
totalNum = cin.nextInt();
numArr = new int[totalNum];
//�婚�搴��
int sumLen = 0;
for(int j=0; j< totalNum; j++){
numArr[j] = cin.nextInt();
sumLen += numArr[j];
}
//������涓������芥病琚�娇�ㄨ���
used = new boolean[totalNum];
for(int j=0; j< totalNum; j++)
used[j] = false;
//���椤绘� 4 ����般�
if(sumLen%4==0){
//���锛��搴��
Arrays.sort(numArr);
int temp;
for(int k=0; k< totalNum/2; k++){
temp = numArr[k];
numArr[k] = numArr[totalNum-1-k];
numArr[totalNum-1-k] = temp;
}
//�峰���ぇ�笺�
int maxNum = numArr[0];
//��疆宸茬��煎ソ��竟�颁负 0��
passNum = 0;
//��ぇ�间��藉ぇ浜���跨� 1/4��
if(maxNum <= sumLen/4){
//寮��娣卞害浼����储��
if(DFS(0, sumLen/4, 0))
System.out.println("yes");
else
System.out.println("no");
}else
System.out.println("no");
}else
System.out.println("no");
}
}

//璁板�宸茬��煎�������搴��杈圭�涓��锛��澶�4 涓��
int passNum = 0;
//�����������惊������绗��瑕��璇���垮害���瑕��涓��搴����
private boolean DFS(int f_num, int f_len, int f_sum){
//褰���板�������搴��绛����
if(f_len == f_sum){
//澧��涓�������竟�般�
passNum++;
//��疆搴�����濮�����绗��
f_sum = 0;
f_num = 0;
//褰��杩��杈规���4 �哥�灏辫�������
if(passNum == 4)
return true;
}
//寮�����涓��灞��
for(int i=f_num; i< totalNum; i++){
//褰���板�涓���板�浜��浜��瑕���垮害�讹�骞朵����娌¤�浣跨���
if(f_sum+numArr[i]<=f_len && !used[i]){
//���璁板�涓哄凡缁�娇�ㄣ�
used[i] = true;
//杩��涓��娆＄������
DFS(i+1, f_len, f_sum+numArr[i]);
//杈规�杈惧� 4 �����烦�哄惊���
if(passNum == 4)
break;
//���浜���㈢����锛����竟�版病��揪��4锛������煎�涓��杈癸��������¤竟锛�互渚挎�璇��浠��缁����
if(f_sum+numArr[i] == f_len)
passNum--;
//���������褰��
used[i] = false;
}
}
//����舵��ヤ�娆℃����濂芥��瑰舰��
if(passNum == 4)
return true;
//杩��澶辫触��
return false;
}
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？