Exhaustive search algorithm that given a list of numbers L tries to find the set M of L with the least cardinality (lowest number of elements) that when added together the result lies within a percent error C of a goal number G, according to the following inequality: (C-1)*G < Sigma(M) < (C+1)*G

permutations_exhaustive.py

def r(m, g, l, d, u, j):
	# print "r iteration: "+str(d)
	if d == len(l)+10:
		return False
	mS = sum(m)
	mL = len(m)
	if mS == g:
		return m
	if mS < g*(1.0+j) and mS > g*(1.0-j):
		return m
	else:
		for ll in l:
			mT = m[:]
			mT.append(ll)
			mTS = sum(mT)
			# print mT
			if mTS == g:
				return mT
			if mTS < g*(1.0+j) and mTS > g*(1.0-j):
				return mT
		# print "mL: "+str(mL)+", U: "+str(u)
		if (mL > u):
			return False
		# Nothing so far try a deeper recursion level
		for ll in l:
			# print "NOT GOING DEEPER"
			mT = m[:]
			mT.append(ll)
			rT = r(mT, g, l, d+1, u, j)
			if rT == False:
				continue
			else:
				return rT
		# Now that nothing happened try another level of deepness
		if mL == u and u > 1:
			return False
		for ll in l:
			# print " GOING DEEPER"
			mT = m[:]
			mT.append(ll)
			rT = r(mT, g, l, d+1, u+1, j)
			if rT == False:
				continue
			else:
				return rT

def executePermutations(goal, list_of_numbers, accuracy):
	return r([0], goal, list_of_numbers, 0, 1, accuracy)

l = [-262.05, 1, -197.66, -197.66, -197.66, -165.04, -130.49, -130.49, -130.49, -130.49, -125.75, -104.14, -79.98, -78.79, -78.79, -78.79, -69.56, -63.03, -47.13, -45.84, -36.85, -35.1, -34.28, -30.84, -28.46, -25.53, -25.3, -25, -24.34, -21.91, -21.15, -18.9, -18.07, -16.8, -15.96, -14.78, -14.66, -14.48, -14.23, -12.5, -10.77, -10.6, -10.6, -10.6, -10.37, -10.37, -9.24, -8.97, -8.7, -8.7, -7.87, -7.6, -7.29, -7.25, -7.24, -7.12, -5.35, -5.35, -4.25, -4.2, -4, -3.5, -3, -3, -2.9, -2.75, -2.74, -2, -1.84, -0.75, -0.5,  121.04, 130.49, 130.49, 130.49, 139.12, 184.12, 197.66, 433.26, 1]

g = 211.10

# l = [0,2,3,4]
# g = 9
result = executePermutations(g, l, 0.06)