[depth first search] Ji suanke: Square

Suppose the sides of the square are a ,b,c ,d,  Each stick Yes 4 A choice ： You can join abcd Any one , You can use dfs

dfs(int index,int a,int b,int c,int d)// Enumerate to index And the current side length is abcd

To make a choice

dfs(index+1,a+p[index],b,c,d;// Join in a

dfs(index+1,a,b+p[index],c,d);// Join in b

dfs(index+1,a,b,c+p[index],d);// Join in c

dfs(index+1,a,b,c,d+p[index]);// Join in d

exit ：

index==n： Reach the empty node in the search tree , Judge abcd Whether the side lengths are equal

prune ：

When side length > Chief, /4 when , It is impossible to form a square , There is no need to search , cut off

  Code ：

#include<iostream>
using namespace std;
int n;
int p[1000];
int sum=0;
bool flag=false;
void dfs(int index,int a,int b,int c,int d){
	if(flag){
		return;
	}
	if(index==n){
		if(a==b&&b==c&&c==d&&d==sum/4){
			cout<<"YES";
			flag=true;
			return;
		}
	}
	if(a>sum/4||b>sum/4||c>sum/4||d>sum/4){
		return;
	}
	dfs(index+1,a+p[index],b,c,d);
	dfs(index+1,a,b+p[index],c,d);
	dfs(index+1,a,b,c+p[index],d);
	dfs(index+1,a,b,c,d+p[index]);
}
int main(){
	cin>>n;

	for(int i=0;i<n;i++){
		cin>>p[i];
		sum+=p[i];
	}
	if(sum%4!=0){
		cout<<"NO";
		return 0;
	}
	else{
		dfs(0,0,0,0,0);
	}
	return 0; 
}