Untitled

Biểu thức Zero
Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và - sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể.

[Input]

Dòng đầu tiên là T số testcase. T dòng tiếp theo là các số tự nhiên N <= 9.

 

[Output]

Mỗi test case in ra “# ” theo sau là số lượng kết quả tìm được mỗi test case. 



[Sample] 

[Input]

1

7

 

[Output]

#1 6

 

Giải thích

1-2-3-4-5+6+7=0

1-2+3+4-5+6-7=0

1-23-45+67=0

1-23+4+5+6+7=0

1+2-3-4+5+6-7=0

1+2-3+4-5-6+7=0

8
2
3
4
5
6
7
8
9

#include <iostream>
using namespace std;

int n;
int ans[30];
int dem;

void BackTrack(int a, int sum, int dem1){
	if(a == n){
		if(sum == 0){
			dem++;
		}
		return;
	}

	if(dem1 == n)
		return;

	int next = a+1;
	for(int i=a+2; i<=n+1; i++){
		BackTrack(i-1, sum+next, dem1+1);
		if(dem1>0)
			BackTrack(i-1, sum-next, dem1+1);
		
		next = next*10+i;
	}
}


int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n;

		dem = 0;
		BackTrack(0, 0, 0);
		cout << "#" << tc << " ";
		cout << dem << endl;
	}
	return 0;
}
#1 0
#2 1
#3 1
#4 1
#5 1
#6 6
#7 10
#8 11