Try, and step back
Some problems ask for all valid arrangements: every combo within budget, every seating plan, a solved Sudoku. Backtracking builds a solution one choice at a time; when a partial solution can't work, it undoes the last choice and tries the next — pruning whole branches early.
Subsets, permutations, pruning
function subsets(items) {
const out = [], current = [];
(function choose(i) {
if (i === items.length) { out.push([...current]); return; }
choose(i + 1); // skip items[i]
current.push(items[i]);
choose(i + 1); // take items[i]
current.pop(); // undo
})(0);
return out;
}
console.log(subsets(["momo", "tea", "lassi"]).map((s) => s.join("+") || "∅"));
function permutations(items) {
const out = [], used = new Array(items.length).fill(false), current = [];
(function place() {
if (current.length === items.length) { out.push(current.join(" ")); return; }
for (let i = 0; i < items.length; i++) {
if (used[i]) continue;
used[i] = true; current.push(items[i]);
place();
used[i] = false; current.pop();
}
})();
return out;
}
console.log(permutations(["A", "B", "C"]));
let calls = 0;
function combosWithin(prices, budget, start = 0, spent = 0) {
calls++;
let count = spent > 0 ? 1 : 0;
for (let i = start; i < prices.length; i++) {
if (spent + prices[i] > budget) break; // prune: prices are sorted
count += combosWithin(prices, budget, i + 1, spent + prices[i]);
}
return count;
}
console.log(combosWithin([50, 60, 90, 120, 180, 220], 200), "combos within 200,", calls, "calls");