/*
 * C Program to find all subsets (multisets) of S that sum
 * to or are equal to W 
 *
 * Name: subsets_sum_to_w
 * Date: 05/22/22
 * Author: yetimach
 */

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
 
#define MAX_SIZE 63 
 
int s[MAX_SIZE]; // main multiset (provided by user)
int subset_s[MAX_SIZE]; // all submultisets saved here|
int binary_array[MAX_SIZE]; // array of 1s and 0s that make up given binary number
							//(This can be done with bits, but this is more clear--and
							//less efficient...)
int binary_len = 0;
int si = 0; // s index
char ch;
int sum_int_array(int *array, int size);
int gen_subset(int *bn, int bnl, int *set, int *subset);
int d_to_b(int dn, int *ba);
int pow2(int);
int get_int_fc(); 
int w; //number to which elements of submultiset must sum (provided by user)
int pss; // possible subsets
int check = 0, not_found = 1, total_num_ss = 0, valid = 0;
int ssi = 0; //subset index 
 
int main()
{
	printf("\n\tDetermine if there is a submultiset of multiset S"
			"\n\tsuch that its elements sum to or are equal to W.\n\n"
			"\n\tEnter elements of S (integers only; max elements 63)\n\t"
			"\"0\" follwed by <enter> to end list.\n\n\telements: ");

	while ((s[si++] = get_int_fc()) != 0){
		if (si >= MAX_SIZE){
			valid = -1;
			break;
		}
	}

	--si;

// Error messages for invalid or empty entries
	if (valid == -1){
		printf("\n\tError: invalid entry.\n\n");
		return -1;
	}
	if (valid == -2){
		printf("\n\tError: no integer entered.\n\n");
		return -1;
	}

	printf("\n\tEnter the value for W followed by <enter>: ");

	w = get_int_fc();

// Error messages for invalid or empty entries
	if (valid == -1){
		printf("\n\tError: invalid entry.\n\n");
		return -1;
	}
	if (valid == -2){
		printf("\n\tError: no integer entered.\n\n");
		return -1;
	}

	pss = pow2(si);

	for (int i = 1; i < pss; i++){
		binary_len = d_to_b(i, binary_array);
		ssi = gen_subset(binary_array, binary_len, s, subset_s);
		check = sum_int_array(subset_s, ssi);
		if (check == 1){
			check = 0;
			total_num_ss++;
			if (not_found)
				printf("\n\tThe following submultisets of S sum to or are equal to %d:\n", w);
			not_found = 0;
			printf("\n\n\tS%-6d{ ", total_num_ss);
			for (int i = 0; i < ssi; i++)
				(i == 0) ? printf("%d", subset_s[i]) : printf(", %d", subset_s[i]);
			printf(" }");
		}
	}
	printf("\n");
	if (not_found)
		printf("\n\tThere is no submultiset of S such that its elements\n\t"
				"sum to or are equal to %d.\n\n", w);
	printf("\n");
	return 0;
}

int sum_int_array(int *array, int size){
	int sum = 0, i = 0;
	while (i < size)
		sum += array[i++];
	if (sum == w)
		return 1;
	else
		return 0;
}

// This has some specific values it sets to the global variable value
// in the event it finds invalid input or no input
// Is it pretty close to fool-proof? 
int get_int_fc(){    // from characters  

     char ch = getchar();
	 if (ch == '\n'){
		 valid = -2;
		 return 0;
	 }
     char chprev = 't';
	 int df = 0;// digit found
     while(!isdigit(ch)){
          chprev = ch;
		  if (ch != ' ' && ch != '-' && ch != '\t' && ch != '\n'){
			  valid = -1;
			  return 0;
		  }
          ch = getchar();
     }
     int num = 0;
     while(isdigit(ch)){
		 df = 1;
         num = num * 10 + ch - '0';
         ch = getchar();
     }
	 if (!isdigit(ch) && ch != '-' && ch != ' ' && ch != '\t' && ch != '\n')
		 valid = -1;
     if (chprev == '-') 
		 num = -num;
	 if (df == 0)
		 valid = -2;

     return num;
 }

//decimal number to binary (stored in array ba)
//return the number places in the number
int d_to_b(int dn, int *ba){
	int  i;    

	for (i = 0; dn > 0; i++){    
		ba[i] = dn % 2;    
		dn = dn / 2;    
	}    

	return i;  
}  


int pow2(int pow){
	int pow2int = 1;
	for (int i = 1; i <= pow; ++i)
		pow2int *= 2;
	return pow2int;
}

int gen_subset(int *bn, int bnl, int *set, int *subset){
	int count = 0; //subset index

	for (int i = 0; i < bnl; i++){
		if (bn[i] == 1){
			subset[count++] = set[i];
		}
	}
	return count;
}