Is there a subset of these 8 values adding up to 47? Trying every subset is 2^8 = 256 sums. Instead, cut the array in half: every subset of the whole is a subset of the left half joined to a subset of the right half, so it is enough to list the sums of each half separately and then look for two that meet at 47.
The code
Enumeration, in Python
def subsets(a, i=0, chosen=None):
if chosen is None: chosen = [] # a fresh list per top-level call
if i == len(a): emit(chosen); return # a leaf: one subset
chosen.append(a[i]) # include a[i]
subsets(a, i + 1, chosen)
chosen.pop() # undo
subsets(a, i + 1, chosen) # exclude a[i]
def permutations(a, i=0):
if i == len(a): emit(a); return # a leaf: one ordering
for k in range(i, len(a)):
a[i], a[k] = a[k], a[i] # put a[k] in position i
permutations(a, i + 1)
a[i], a[k] = a[k], a[i] # undo, so the next k starts clean
def combinations(a, k, start=0, chosen=None):
if chosen is None: chosen = [] # a fresh list per top-level call
if len(chosen) == k: emit(chosen); return # a leaf: one combination
for i in range(start, len(a)): # only later indices: no repeats, no reorderings
chosen.append(a[i])
combinations(a, k, i + 1, chosen)
chosen.pop() # undo
def combination_sum(a, target, start=0, chosen=None):
if chosen is None: chosen = [] # a fresh list per top-level call
if target == 0: emit(chosen); return # the picks add up exactly
for i in range(start, len(a)): # start at i again: a candidate may repeat
if a[i] > target: continue # prune: this pick alone overshoots
chosen.append(a[i])
combination_sum(a, target - a[i], i, chosen)
chosen.pop() # undo
def meet_in_the_middle(a, target):
left = a[:len(a) // 2]; right = a[len(a) // 2:]
left_sums = subset_sums(left) # 2^(n/2) sums instead of 2^n subsets
right_sums = sorted(subset_sums(right)) # sorted once, so each lookup is a binary search
for s in left_sums:
j = bisect_left(right_sums, target - s)
if j < len(right_sums) and right_sums[j] == target - s: return True # the halves meet
return False
def subset_sums(a): return [sum(a[i] for i in range(len(a)) if m >> i & 1 == 1) for m in range(1 << len(a))]
Enumeration, in JavaScript
function subsets(a, i = 0, chosen = []) {
if (i === a.length) { emit(chosen); return; } // a leaf: one subset
chosen.push(a[i]); // include a[i]
subsets(a, i + 1, chosen);
chosen.pop(); // undo
subsets(a, i + 1, chosen); // exclude a[i]
}
function permutations(a, i = 0) {
if (i === a.length) { emit(a); return; } // a leaf: one ordering
for (let k = i; k < a.length; k++) {
[a[i], a[k]] = [a[k], a[i]]; // put a[k] in position i
permutations(a, i + 1);
[a[i], a[k]] = [a[k], a[i]]; // undo, so the next k starts clean
}
}
function combinations(a, k, start = 0, chosen = []) {
if (chosen.length === k) { emit(chosen); return; } // a leaf: one combination
for (let i = start; i < a.length; i++) { // only later indices: no repeats, no reorderings
chosen.push(a[i]);
combinations(a, k, i + 1, chosen);
chosen.pop(); // undo
}
}
function combinationSum(a, target, start = 0, chosen = []) {
if (target === 0) { emit(chosen); return; } // the picks add up exactly
for (let i = start; i < a.length; i++) { // start at i again: a candidate may repeat
if (a[i] > target) continue; // prune: this pick alone overshoots
chosen.push(a[i]);
combinationSum(a, target - a[i], i, chosen);
chosen.pop(); // undo
}
}
function meetInTheMiddle(a, target) {
const half = Math.floor(a.length / 2);
const left = a.slice(0, half); const right = a.slice(half);
const leftSums = subsetSums(left); // 2^(n/2) sums instead of 2^n subsets
const rightSums = subsetSums(right).sort((x, y) => x - y); // sorted once, so each lookup is a binary search
const has = (v) => { // no stdlib binary search in JS, so here it is
let lo = 0, hi = rightSums.length - 1;
while (lo <= hi) {
const m = (lo + hi) >> 1;
if (rightSums[m] === v) return true;
if (rightSums[m] < v) lo = m + 1; else hi = m - 1;
}
return false;
};
for (const s of leftSums) if (has(target - s)) return true; // the halves meet
return false;
}
function subsetSums(a) { return Array.from({ length: 1 << a.length }, (_, m) => a.reduce((sum, v, i) => ((m >> i) & 1) === 1 ? sum + v : sum, 0)); }
Enumeration, in Kotlin
fun subsets(a: IntArray, i: Int = 0, chosen: MutableList<Int> = mutableListOf()) {
if (i == a.size) { emit(chosen); return } // a leaf: one subset
chosen += a[i] // include a[i]
subsets(a, i + 1, chosen)
chosen.removeLast() // undo
subsets(a, i + 1, chosen) // exclude a[i]
}
fun permutations(a: IntArray, i: Int = 0) {
if (i == a.size) { emit(a); return } // a leaf: one ordering
for (k in i until a.size) {
a.swap(i, k) // put a[k] in position i
permutations(a, i + 1)
a.swap(i, k) // undo, so the next k starts clean
}
}
fun combinations(a: IntArray, k: Int, start: Int = 0, chosen: MutableList<Int> = mutableListOf()) {
if (chosen.size == k) { emit(chosen); return } // a leaf: one combination
for (i in start until a.size) { // only later indices: no repeats, no reorderings
chosen += a[i]
combinations(a, k, i + 1, chosen)
chosen.removeLast() // undo
}
}
fun combinationSum(a: IntArray, target: Int, start: Int = 0, chosen: MutableList<Int>) {
if (target == 0) { emit(chosen); return } // the picks add up exactly
for (i in start until a.size) { // start at i again: a candidate may repeat
if (a[i] > target) continue // prune: this pick alone overshoots
chosen += a[i]
combinationSum(a, target - a[i], i, chosen)
chosen.removeLast() // undo
}
}
fun meetInTheMiddle(a: IntArray, target: Int): Boolean {
val left = a.copyOfRange(0, a.size / 2); val right = a.copyOfRange(a.size / 2, a.size)
val leftSums = subsetSums(left) // 2^(n/2) sums instead of 2^n subsets
val rightSums = subsetSums(right).sorted() // sorted once, so each lookup is a binary search
for (s in leftSums) if (rightSums.binarySearch(target - s) >= 0) return true // the halves meet
return false
}
fun subsetSums(a: IntArray) = (0 until (1 shl a.size)).map { m -> a.indices.filter { m shr it and 1 == 1 }.sumOf { a[it] } }