A permutation is one ordering of a collection, and a subset is any selection from it — from picking nothing up to picking everything. This question asks you to generate all of both for an array of distinct values: every permutation (there are n! of them) and every subset (the power set, 2^n of them), packaged on one object as permutationsSubsets = { permutations, subsets }. The reason to pair them is that a single backtracking template — choose an option, recurse, then undo the choice — produces both; only the meaning of a choice changes. See Permutation and Power set for background.
permutationsSubsets.permutations(arr) // distinct items -> array of all n! orderings
permutationsSubsets.subsets(arr) // distinct items -> array of all 2^n subsetsBoth return an array of arrays; each inner array is a brand-new array.
permutationsSubsets.permutations([1, 2, 3]);
// six arrays, in some order:
// [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
permutationsSubsets.subsets([1, 2, 3]);
// eight arrays, in some order:
// [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]permutations([]) is [[]] (one empty ordering) and subsets([]) is [[]] (the empty array is the only subset). Both have exactly one element, not zero.n! and 2^n blow up quickly (10! is over three million), so this is meant for small n. No libraries — build both yourself.We are generating two classic families — every ordering of an array and every subset of it — from one small recursive template that chooses an option, recurses, and then puts the option back.
Given an array of distinct values like [1, 2, 3], you want two different exhaustive lists. The permutations are every way to arrange all the items in a row — [1,2,3], [1,3,2], and so on, n! of them. The subsets are every way to pick some of the items regardless of order, from the empty array [] all the way up to the whole thing [1,2,3] — 2^n of them, together called the power set. The useful observation is that both come from the same idea: make one choice at a time, explore everything that follows, then take the choice back and try the next.
Picture the work as a tree of decisions. You start at the root with an empty hand, and at each level you make one choice; every path from the root down to a leaf is one finished answer. The two problems differ only in what a choice is. For permutations, a choice is which unused element to place next, so a node with three items left fans into three branches and the tree ends in n! leaves. For subsets, a choice is in or out for one element, so every node splits in two and the tree ends in 2^n leaves.
For subsets alone there is a shortcut that skips recursion entirely: start with a list holding just the empty subset, then fold in one element at a time. Each time you meet a new element, every subset you already have spawns a copy that also includes it — so the count doubles at every step, from 1 to 2 to 4 to 8.
function subsetsByDoubling(arr) {
let result = [[]];
for (const x of arr) {
// Every existing subset spawns a copy that also includes x.
result = result.concat(result.map((sub) => [...sub, x]));
}
return result;
}This is correct and compact, and the doubling makes the 2^n count plain to see. But it is a one-off: it does not give you permutations, and it does not stretch to nearby questions like combinations (every subset of a fixed size k) or arrangements with adjacency constraints. Those all fall out of one recursive template instead — so it pays to learn that template here, on the two cleanest examples, rather than memorizing a separate trick per problem.
const permutationsSubsets = {
// Every ordering of arr. A "choice" here is any element not yet used.
permutations(arr) {
const result = [];
const current = []; // the ordering built so far
const used = new Array(arr.length).fill(false); // which indices are taken
function backtrack() {
// A full-length path is one complete ordering — record a COPY of it.
if (current.length === arr.length) {
result.push(current.slice());
return;
}
for (let i = 0; i < arr.length; i++) {
if (used[i]) continue; // skip elements already placed in this path
used[i] = true; // choose arr[i]
current.push(arr[i]);
backtrack(); // recurse on the smaller sub-problem
current.pop(); // undo the choice...
used[i] = false; // ...so the next iteration can try a different element
}
}
backtrack();
return result;
},
// Every subset of arr. A "choice" here is which later element to add next.
subsets(arr) {
const result = [];
const current = []; // the subset built so far
function backtrack(start) {
// Every node on the way down is itself a valid subset — record a COPY.
result.push(current.slice());
// Only look from `start` onward, so each subset is built in one fixed
// order and never regenerated as a reshuffle of the same elements.
for (let i = start; i < arr.length; i++) {
current.push(arr[i]); // include arr[i]
backtrack(i + 1); // recurse on the elements after i
current.pop(); // undo — now explore the paths that skip arr[i]
}
}
backtrack(0);
return result;
},
};
module.exports = { permutationsSubsets };Read the two backtrack functions side by side and the skeleton is identical: loop over the candidate choices, apply one by pushing it onto current, recurse, then undo it by popping it back off. Only two knobs move. The first is what a valid next choice is — for permutations it is any element not yet used, so the loop starts at 0 and skips taken indices; for subsets it is any element after the last one taken, so the loop starts at start. The second is when to record a result — a permutation is only finished when the path is full length, while every partial subset path is already a subset, so subsets records on entry to every call. Everything else, including the all-important current.slice() and the pop(), is shared.
Trace permutations([1, 2, 3]). Start at the root with an empty path and nothing used, and take the leftmost branch whenever you can:
1 (path [1]), then 2 (path [1,2]), then 3 (path [1,2,3]). The path is full, so record [1,2,3], then pop the 3 and unmark it.[1,2] the loop has no elements left, so it returns and undoes 2. Back at path [1], the next unused element is 3: choose 3 (path [1,3]), then 2 (path [1,3,2]) — record it.2 yields [2,1,3] and [2,3,1]; starting with 3 yields [3,1,2] and [3,2,1]. Six leaves, six orderings.Now subsets([1, 2, 3]). The code records the path the instant it enters backtrack, so the empty array [] is captured first. Then it adds 1 and recurses ([1]), adds 2 ([1,2]), adds 3 ([1,2,3]); unwinding and continuing the loops reaches [1,3], then [2], [2,3], and finally [3] — all eight subsets.
The include-or-exclude tree below shows those same eight subsets a different way: read each element in turn and decide out (left) or in (right). Three yes-or-no decisions give 2^3 = 8 leaves. The start-index loop reaches those same eight with one twist — because it only ever adds elements to the right of the last one, it builds [1,2] exactly once and never rebuilds it as [2,1], which is precisely why a subset is unordered.
result.push(current) pushes a reference to the one array you keep mutating, so as the recursion undoes its choices every stored result empties out and you finish with a list of identical arrays. current.slice() snapshots the path so each result stands alone.pop() (and used[i] = false for permutations) after the recursive call is what lets the next loop iteration start from a clean path. Forget it and choices pile up: the path never shrinks, and you generate garbage or overflow the stack.current.length === arr.length guard; a subset is valid at every step, so it records at the top of every call. Copy the permutations base case into subsets and you get back only the full array; do the reverse and you get every prefix of a single ordering.[1, 1, 2], this code emits duplicate permutations and subsets because it treats the two 1s as different. De-duplicating needs the sort-and-skip trick below.k) — the subsets template already walks every size. Collect only the paths where current.length === k, and stop descending once the elements left cannot reach k. That small change turns the power-set walk into the standard k-sized-combination generator.[1, 1, 2] produce each distinct result once, sort the input, then at each level skip a candidate equal to the previous one you already tried at that level (if (i > start && arr[i] === arr[i - 1]) continue;). Sorting brings equal values next to each other so the skip is one comparison.nextPermutation algorithm rewrites an array into the next-larger ordering in O(n) time and O(1) extra space, so you can walk all n! orderings one at a time without ever storing them. It is how you enumerate permutations when the full list would not fit in memory.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
A permutation is one ordering of a collection, and a subset is any selection from it — from picking nothing up to picking everything. This question asks you to generate all of both for an array of distinct values: every permutation (there are n! of them) and every subset (the power set, 2^n of them), packaged on one object as permutationsSubsets = { permutations, subsets }. The reason to pair them is that a single backtracking template — choose an option, recurse, then undo the choice — produces both; only the meaning of a choice changes. See Permutation and Power set for background.
permutationsSubsets.permutations(arr) // distinct items -> array of all n! orderings
permutationsSubsets.subsets(arr) // distinct items -> array of all 2^n subsetsBoth return an array of arrays; each inner array is a brand-new array.
permutationsSubsets.permutations([1, 2, 3]);
// six arrays, in some order:
// [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
permutationsSubsets.subsets([1, 2, 3]);
// eight arrays, in some order:
// [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]permutations([]) is [[]] (one empty ordering) and subsets([]) is [[]] (the empty array is the only subset). Both have exactly one element, not zero.n! and 2^n blow up quickly (10! is over three million), so this is meant for small n. No libraries — build both yourself.We are generating two classic families — every ordering of an array and every subset of it — from one small recursive template that chooses an option, recurses, and then puts the option back.
Given an array of distinct values like [1, 2, 3], you want two different exhaustive lists. The permutations are every way to arrange all the items in a row — [1,2,3], [1,3,2], and so on, n! of them. The subsets are every way to pick some of the items regardless of order, from the empty array [] all the way up to the whole thing [1,2,3] — 2^n of them, together called the power set. The useful observation is that both come from the same idea: make one choice at a time, explore everything that follows, then take the choice back and try the next.
Picture the work as a tree of decisions. You start at the root with an empty hand, and at each level you make one choice; every path from the root down to a leaf is one finished answer. The two problems differ only in what a choice is. For permutations, a choice is which unused element to place next, so a node with three items left fans into three branches and the tree ends in n! leaves. For subsets, a choice is in or out for one element, so every node splits in two and the tree ends in 2^n leaves.
For subsets alone there is a shortcut that skips recursion entirely: start with a list holding just the empty subset, then fold in one element at a time. Each time you meet a new element, every subset you already have spawns a copy that also includes it — so the count doubles at every step, from 1 to 2 to 4 to 8.
function subsetsByDoubling(arr) {
let result = [[]];
for (const x of arr) {
// Every existing subset spawns a copy that also includes x.
result = result.concat(result.map((sub) => [...sub, x]));
}
return result;
}This is correct and compact, and the doubling makes the 2^n count plain to see. But it is a one-off: it does not give you permutations, and it does not stretch to nearby questions like combinations (every subset of a fixed size k) or arrangements with adjacency constraints. Those all fall out of one recursive template instead — so it pays to learn that template here, on the two cleanest examples, rather than memorizing a separate trick per problem.
const permutationsSubsets = {
// Every ordering of arr. A "choice" here is any element not yet used.
permutations(arr) {
const result = [];
const current = []; // the ordering built so far
const used = new Array(arr.length).fill(false); // which indices are taken
function backtrack() {
// A full-length path is one complete ordering — record a COPY of it.
if (current.length === arr.length) {
result.push(current.slice());
return;
}
for (let i = 0; i < arr.length; i++) {
if (used[i]) continue; // skip elements already placed in this path
used[i] = true; // choose arr[i]
current.push(arr[i]);
backtrack(); // recurse on the smaller sub-problem
current.pop(); // undo the choice...
used[i] = false; // ...so the next iteration can try a different element
}
}
backtrack();
return result;
},
// Every subset of arr. A "choice" here is which later element to add next.
subsets(arr) {
const result = [];
const current = []; // the subset built so far
function backtrack(start) {
// Every node on the way down is itself a valid subset — record a COPY.
result.push(current.slice());
// Only look from `start` onward, so each subset is built in one fixed
// order and never regenerated as a reshuffle of the same elements.
for (let i = start; i < arr.length; i++) {
current.push(arr[i]); // include arr[i]
backtrack(i + 1); // recurse on the elements after i
current.pop(); // undo — now explore the paths that skip arr[i]
}
}
backtrack(0);
return result;
},
};
module.exports = { permutationsSubsets };Read the two backtrack functions side by side and the skeleton is identical: loop over the candidate choices, apply one by pushing it onto current, recurse, then undo it by popping it back off. Only two knobs move. The first is what a valid next choice is — for permutations it is any element not yet used, so the loop starts at 0 and skips taken indices; for subsets it is any element after the last one taken, so the loop starts at start. The second is when to record a result — a permutation is only finished when the path is full length, while every partial subset path is already a subset, so subsets records on entry to every call. Everything else, including the all-important current.slice() and the pop(), is shared.
Trace permutations([1, 2, 3]). Start at the root with an empty path and nothing used, and take the leftmost branch whenever you can:
1 (path [1]), then 2 (path [1,2]), then 3 (path [1,2,3]). The path is full, so record [1,2,3], then pop the 3 and unmark it.[1,2] the loop has no elements left, so it returns and undoes 2. Back at path [1], the next unused element is 3: choose 3 (path [1,3]), then 2 (path [1,3,2]) — record it.2 yields [2,1,3] and [2,3,1]; starting with 3 yields [3,1,2] and [3,2,1]. Six leaves, six orderings.Now subsets([1, 2, 3]). The code records the path the instant it enters backtrack, so the empty array [] is captured first. Then it adds 1 and recurses ([1]), adds 2 ([1,2]), adds 3 ([1,2,3]); unwinding and continuing the loops reaches [1,3], then [2], [2,3], and finally [3] — all eight subsets.
The include-or-exclude tree below shows those same eight subsets a different way: read each element in turn and decide out (left) or in (right). Three yes-or-no decisions give 2^3 = 8 leaves. The start-index loop reaches those same eight with one twist — because it only ever adds elements to the right of the last one, it builds [1,2] exactly once and never rebuilds it as [2,1], which is precisely why a subset is unordered.
result.push(current) pushes a reference to the one array you keep mutating, so as the recursion undoes its choices every stored result empties out and you finish with a list of identical arrays. current.slice() snapshots the path so each result stands alone.pop() (and used[i] = false for permutations) after the recursive call is what lets the next loop iteration start from a clean path. Forget it and choices pile up: the path never shrinks, and you generate garbage or overflow the stack.current.length === arr.length guard; a subset is valid at every step, so it records at the top of every call. Copy the permutations base case into subsets and you get back only the full array; do the reverse and you get every prefix of a single ordering.[1, 1, 2], this code emits duplicate permutations and subsets because it treats the two 1s as different. De-duplicating needs the sort-and-skip trick below.k) — the subsets template already walks every size. Collect only the paths where current.length === k, and stop descending once the elements left cannot reach k. That small change turns the power-set walk into the standard k-sized-combination generator.[1, 1, 2] produce each distinct result once, sort the input, then at each level skip a candidate equal to the previous one you already tried at that level (if (i > start && arr[i] === arr[i - 1]) continue;). Sorting brings equal values next to each other so the skip is one comparison.nextPermutation algorithm rewrites an array into the next-larger ordering in O(n) time and O(1) extra space, so you can walk all n! orderings one at a time without ever storing them. It is how you enumerate permutations when the full list would not fit in memory.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.