---
# System prepended metadata

title: Untitled

---

#include <stdio.h>
#include <stdlib.h>


int num = 0;
//2つの数の和がXになるものを探す関数
void combi_sum_two(int A[], int p, int w, int n, int r, int X, int array[]);
//いくつかの数の和がXになるものを探す関数
void combi_sum(int A[], int p, int w, int n, int r, int X, int array[]);
//2つの数の差がXになるものを探す関数
void combi_difference(int A[], int p, int w, int n, int r, int X, int array[]);
//2つの数を足し引きしてXになるものを探す関数
void combi_sum_difference_two(int A[], int p, int w, int n, int r, int X, int array[]);
//いくつかの数を足し引きしてXになるものを探す関数
void combi_sum_difference(int A[], int p, int w, int n, int r, int X, int array[]);

int main(void)
{
	//基本問題1
	int i;
	int N = 0;
	int r = 2;
	int X = 0;
	int K[190];
	int array[20];
	printf("<基本問題1>\n入力する整数の個数N(2<N<21)を入力してください。\nN=");
	scanf_s("%d", &N);
	if (N < 3 || N > 20) {
		printf("N=%dは2<N<21を満たしていません。プログラムを終了します。\n", N);
		exit(0);
	}
	printf("%d個の整数を入力してください。\n", N);
	for (i = 0; i < N; i++) {
		scanf_s("%d", &array[i]);
	}
	printf("2つの数値の和Xがいくつになる組み合わせを探しますか。\nX=");
	scanf_s("%d", &X);
	combi_sum_two(K, r, N - r, N, r, X, array);

	//基本問題2
	//初期化
	num = 0;
	N = 0;
	r = 0;
	X = 0;
	printf("<基本問題2>\n入力する整数の個数N(2<N<21)を入力してください。\nN=");
	scanf_s("%d", &N);
	if (N < 3 || N > 20) {
		printf("N=%dは2<N<21を満たしていません。プログラムを終了します。\n", N);
		exit(0);
	}
	printf("%d個の整数を入力してください。\n", N);
	for (i = 0; i < N; i++) {
		scanf_s("%d", &array[i]);
	}
	printf("いくつかの数値の和Xがいくつになる組み合わせを探しますか。\nX=");
	scanf_s("%d", &X);
	combi_sum(K, r, N - r, N, r, X, array);

	//基本問題3
	//初期化
	num = 0;
	N = 0;
	r = 2;
	X = 0;
	printf("<基本問題3>\n入力する整数の個数N(2<N<21)を入力してください。\nN=");
	scanf_s("%d", &N);
	if (N < 3 || N > 20) {
		printf("N=%dは2<N<21を満たしていません。プログラムを終了します。\n", N);
		exit(0);
	}
	printf("%d個の整数を入力してください。\n", N);
	for (i = 0; i < N; i++) {
		scanf_s("%d", &array[i]);
	}
	printf("2つの数値の差Xがいくつになる組み合わせを探しますか。\nX=");
	scanf_s("%d", &X);
	combi_difference(K, r, N - r, N, r, X, array);

	//基本課題4
	//初期化
	num = 0;
	N = 0;
	r = 0;
	X = 0;
	printf("<基本問題4>\n入力する整数の個数N(2<N<21)を入力してください。\nN=");
	scanf_s("%d", &N);
	if (N < 3 || N > 20) {
		printf("N=%dは2<N<21を満たしていません。プログラムを終了します。\n", N);
		exit(0);
	}
	printf("%d個の整数を入力してください。\n", N);
	for (i = 0; i < N; i++) {
		scanf_s("%d", &array[i]);
	}
	printf("いくつかの数値を足し引きした結果Xがいくつになるものを探しますか。\nX=");
	scanf_s("%d", &X);
	combi_sum_difference(K, r, N - r, N, r, X, array);
	return 0;
}


//2つの数の和がXになるものを探す関数
void combi_sum_two(int A[], int p, int w, int N, int r, int X, int array[])
{
	//ループ脱出条件
	if (p > 0)
	{
		int i;
		for (i = 0; i <= w; i++){
			A[p] = i;
			combi_sum_two(A, p - 1, w - i, N, r, X, array); //再起
		}
	}
	else {
		int i, j, m;
		int sum = 0;
		int array_index[20]; //0と1を記録する配列
		num++;
		printf("%d:\t", num);
		m = 0;
		for (i = 1; i <= r; i++) {
			for (j = 0; j < A[i]; j++, m++) {
				array_index[m] = 0;
			}
			array_index[m] = 1;
			//1を出力した場合、和をとる
			sum += array[m];
			m++;
		}
		for (; m < N; m++) {
			array_index[m] = 0;
		}
		//0と1を出力
		for (j = 0; j < m; j++) {
			printf("%d", array_index[j]);
		}
		//和を出力
		printf("\tsum = %d", sum);
		//和とXが同値なら1を出力した位置にある数値を出力
		if (sum == X) {
			printf("\t和が%dになる組み合わせは", X);
			for (j = 0; j < N; j++) {
				if (array_index[j] == 1) {
					printf(",%d", array[j]);
				}
			}
			printf("です。");
		}
		printf("\n");
	}
}

//いくつかの数の和がXになるものを探す関数
void combi_sum(int A[], int p, int w, int N, int r, int X, int array[])
{
	for (r = 1; r <= N; r++) {
		combi_sum_two(A, r, N - r, N, r, X, array); //2つの数の和がXになるものを探す関数
	}
}

//2つの数の差がXになるものを探す関数
void combi_difference(int A[], int p, int w, int N, int r, int X, int array[])
{
	if (p > 0)
	{
		int i;
		for (i = 0; i <= w; i++){
			A[p] = i;
			combi_difference(A, p - 1, w - i, N, r, X, array);
		}
	}
	else {
		int i, j, m;
		int count = 0;
		int difference_two[2];
		int array_index[20];
		num++;
		printf("%d:\t", num);
		m = 0;
		for (i = 1; i <= r; i++) {
			for (j = 0; j < A[i]; j++, m++) {
				printf("0");
				array_index[m] = 0;
			}
			printf("1");
			array_index[m] = 1;
			difference_two[count] = array[m];
			count++;
			m++;
		}
		for (; m < N; m++) {
			printf("0");
			array_index[m] = 0;
		}
		printf("\tABS(difference) = %d", abs(difference_two[0] - difference_two[1]));
		if (abs(difference_two[0] - difference_two[1]) == abs(X)) {
			printf("\t2つの数の差が%dになる組み合わせは", X);
			for (j = 0; j < N; j++) {
				if (array_index[j] == 1) {
					printf(",%d", array[j]);
				}
			}
			printf("です。");
		}
		printf("\n");
	}
}

//2つの数を足し引きしてXになるものを探す関数
void combi_sum_difference_two(int A[], int p, int w, int N, int r, int X, int array[])
{
	//ループ脱出条件
	if (p > 0)
	{
		int i;
		for (i = 0; i <= w; i++){
			A[p] = i;
			combi_sum_difference_two(A, p - 1, w - i, N, r, X, array); //再起
		}
	}
	else {
		int i, j, m;
		int sum = 0;
		int count = 0;
		int array_index[20]; //0と1を記録する配列
		int array_suuti[20]; //1を出力した位置の数値を受け取る配列
		num++;
		printf("%d:\t", num);
		m = 0;
		//array_suutiの初期化
		for (i = 0; i < N; i++) {
			array_suuti[i] = 0;
		}
		for (i = 1; i <= r; i++) {
			for (j = 0; j < A[i]; j++, m++) {
				array_index[m] = 0;
			}
			array_index[m] = 1;
			//1を出力した位置の数値をarray_suutiに格納
			array_suuti[count] = array[m];
			count++;
			m++;
		}
		for (; m < N; m++) {
			array_index[m] = 0;
		}
		//0と1を出力
		for (i = 0; i < m; i++) {
			printf("%d", array_index[i]);
		}
		printf("\t");
		//1を出力した位置の数値の足し引きをbit全探索
		int bit;
		int S[20];
		for (bit = 0; bit < (1 << count); bit++) {
			// Sの初期化
			for (j = 0; j < count; j++) {
				S[j] = 0;
			}
			sum = 0;
			for (j = 0; j < count; j++) {
				if (bit & (1 << j)) {
					S[j] = 1;
					sum += array_suuti[j]; //1の場合、数値を足す
				}
				else{
					sum += (-1) * (array_suuti[j]); //1でない場合、数値を引く
				}
			}			
			if (sum == X) {
				printf("\t足し引きして%dになる数値の組み合わせは", X);
				for (j = 0; j < count; j++) {
					printf(",%d ", array_suuti[j]);
				}
				printf("です。");
				break;
			}
		}
		printf("\n");
	}
}

//いくつかの数を足し引きしてXになるものを探す関数
void combi_sum_difference(int A[], int p, int w, int N, int r, int X, int array[])
{
	for (r = 1; r <= N; r++) {
		combi_sum_difference_two(A, r, N - r, N, r, X, array); //2つの数を足し引きしてXになるものを探す関数
	}
}