square.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.*;


/**
 * ID:2362
 * DFS. k为从几开始循环，S是当前总数，c为考虑第几条边。对于一条边，先放还是后放没有关系，因此放第i条边时不考虑i之前的边
 * @author yhm
 *
 */
public class Square {

	static int sum;
	static boolean Find;
	static int size;

	
	static int[] Num;
	static boolean[] Use;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			size = cin.nextInt();
			Num = new int[size];
			Use = new boolean[size];
			Arrays.fill(Use, false);
			sum=0;
			for(int j=0;j<size;j++){
				Num[j] = cin.nextInt();
				sum+=Num[j];
			}
			if(sum%4!=0){
				System.out.println("no");
			}
			else{
				sum = sum/4;
				Find = false;
				DFS(0,0,0);
				System.out.println(Find?"yes":"no");
			}

			
		}

	}

	static void DFS(int k, int S, int c)
	{
	    if(S == sum)
	    {
	        c++;
	        if(c == 3) { Find = true; return ;}
	        else
	        {
	            DFS(0, 0, c);
	        }
	    }
	    else
	    {
	        for(int i = k; i < size && !Find; i++)
	        {
	            if(!Use[i] && (S+Num[i]) <= sum)
	            {
	                Use[i] = true;
	                DFS(i+1, S+Num[i], c);
	                Use[i] = false;
	            }
	        }
	    }
	}
	
}