There’s a class of problems that deal with subsets, permutations and so on. Let’s find a way to generate a power set of a set with distinct elements. This is a problem #78 on LeetCode.

What is backtracking?

According to Wikipedia, backtracking is a general algorithm (or an idea) of searching all the solutions by reducing the search space. It’s really close to brute force, try all the options. But at some point we need to take a step back (backtrack) if we cannot proceed.

Some classical problems that can be solved by the backtracking are:

So, back to the power sets

So, the task is, given a set, find the power set of that set:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

I once stumbled upon the following snippet:

search(int k) {
  if (k == n) {
    res.push(subset)
  } else {
    search(k+1);
    subset.push(k);
    search(k+1);
    subset.pop();
  }
}

This piece of code relies heavily on the variables outside of the scope of the search function. However, I didn’t understand this code because of the marked lines. It is recursive, but this recursion relies on the mutable variable subset.

If we employ immutability here we could get a slightly better code:

var subsets = function (nums) {
  let res = [];
  let n = nums.length;

  function search(i, acc = []) {
    if (i == n) {
      res.push(acc);
    } else {
      search(i + 1, acc);
      search(i + 1, acc.concat([nums[i]]));
    }
  }

  search(0);
  return res;
};