#include <stdio.h>
#include <math.h>

extern "C" unsigned char _BitScanForward (unsigned *, unsigned __int32); 
#pragma intrinsic (_BitScanForward)

static unsigned looking4sum_gray (unsigned length, const double array[], const double target)
{
	// минимальная проверка
	if (length < 1|target <= 0.0)
		return 0;

	double flip[32];
	unsigned pos, i, j;
	char tab[32];
	double sum;
	
	// компируем элементы, фильтруя ненужные и проверяя единичные случаи
	sum = 0.0; i = length; length = 0; do {
		i--;
		if (array[i] == target)
			return 1u << i;
		if (array[i] < target) {
			sum += array[i];
			tab[length] = i;
			flip[length] = array[i];
			if (++length > 32)
				return 0;
		}
	} while (i);

	if (length < 2)
		return 1u << tab[0];

	// проверяем парные случаи, это несравнимо быстрее полного перебора
	i = 0; do {
		j = i + 1; do {
			if (flip[i] + flip[j] == target)
				return (1u << tab[i]) + (1u << tab[j]);
		} while (++j < length);
	} while (++i < length - 1);

	// счетчик для перебора
	pos = (1ul << length) - 1;
	if (length == 32)
		pos = ~0u;

	unsigned best_gray, gray;
	if (sum <= target)
		// наилучший вариант - сумма всех слагаемых меньших target
		best_gray = pos;
	else {
		// полный перебор кодом Грея
		double best_diff = fabs (target);
		gray = best_gray = 0; sum = 0.0; do {
			j = gray;
			gray = pos ^ (pos >> 1);
			j ^= gray;
			_BitScanForward (&i, j);
			sum += flip[i];
			flip[i] = -flip[i];
			double diff = fabs (sum - target);
			if (diff < best_diff) {
				best_gray = gray;
				best_diff = diff;
				if (diff == 0.0)
					break;
			}
		} while (--pos);
	}

	// конвертируем индексы слагаемых (с учетом пропусков и обратного порядка)
	gray = i = 0; do {
		if (best_gray & 1)
			gray |= 1u << tab[i];
		i++;
	} while (best_gray >>= 1);
	return gray;
}

static unsigned looking4sum_gray_test (const unsigned length, const double array[], const double target)
{
	unsigned gray = looking4sum_gray (length, array, target);
	double test = 0.0;
	for (unsigned i = 0; gray; i++) {
		if (gray & 1)
			test += array[i];
		gray >>= 1;
	}

	printf ("target %f, result %f, error %f\n", target, test, target - test);
	return gray;
}

int main (int argc, char* argv[])
{
	static const double test_array[32] = {
		6015.8208, 9489.67893, 83.219879, 848.9457, 163.978846,
		371946.92, 741.743057, 72464.5683, 45.675712, 56.129234, 89412.3127,
		479.74316, 9874.652, 17649.589146, 6565.98146, 79.846252, 854764,
		4523.574, 43576.945, 86.9871396, 451513.3424, 52.1619388, 131624,
		464.9687, 74592.1453, 697.1834745, 637.195, 44535,
		3476.91274, 4123.1237, 3102.982, 769.8498
	};

	looking4sum_gray_test (32, test_array, 23534.9999);
	return 0;
}