#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になるものを探す関数
}
}