SimuVedaAlgorithms Lab Open in the lab

Backtracking / Intermediate

Subsets Visualizer

For each value, make a choice: include it or skip it. Go deeper, then undo the choice and try the other branch.

Start the Subsets simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n·2ⁿ)
Average timeO(n·2ⁿ)
Worst timeO(n·2ⁿ)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Choose to include 1.
  2. Choose to include 2.
  3. Choose to include 3.
  4. Reached the end. Save [1, 2, 3].
  5. Undo: remove 3, then try the branch that skips it.
  6. Reached the end. Save [1, 2].
  7. Undo: remove 2, then try the branch that skips it.
  8. Choose to include 3.
  9. Reached the end. Save [1, 3].
  10. Undo: remove 3, then try the branch that skips it.
  11. Reached the end. Save [1].
  12. Undo: remove 1, then try the branch that skips it.
  13. Choose to include 2.
  14. Choose to include 3.
  15. Reached the end. Save [2, 3].
  16. Undo: remove 3, then try the branch that skips it.
  17. Reached the end. Save [2].
  18. Undo: remove 2, then try the branch that skips it.
  19. Choose to include 3.
  20. Reached the end. Save [3].
  21. Undo: remove 3, then try the branch that skips it.
  22. Reached the end. Save [].
  23. Done. 8 subsets in total, which is 2^3.

Try it with your own input →

Backtracking: subsets in Java, Python, C++, C and JavaScript

void backtrack(int i, List<Integer> path) {
  if (i == nums.length) {
    result.add(new ArrayList<>(path));
    return;
  }
  path.add(nums[i]);
  backtrack(i + 1, path);
  path.remove(path.size() - 1);
  backtrack(i + 1, path);
}
def backtrack(i, path):
    if i == len(nums):
        result.append(path[:])
        return
    path.append(nums[i])
    backtrack(i + 1, path)
    path.pop()
    backtrack(i + 1, path)
void backtrack(int i, vector<int>& path) {
  if (i == (int)nums.size()) {
    result.push_back(path);
    return;
  }
  path.push_back(nums[i]);
  backtrack(i + 1, path);
  path.pop_back();
  backtrack(i + 1, path);
}
int nums[20], n, path[20], plen;

void backtrack(int i) {
  if (i == n) {
    record(path, plen);   /* save a copy of path[0..plen-1] */
    return;
  }
  path[plen++] = nums[i];
  backtrack(i + 1);
  plen--;
  backtrack(i + 1);
}
function backtrack(i, path) {
  if (i === nums.length) {
    result.push([...path]);
    return;
  }
  path.push(nums[i]);
  backtrack(i + 1, path);
  path.pop();
  backtrack(i + 1, path);
}

In an interview

LeetCode 78, Subsets. The same template solves 46 Permutations, 39 Combination Sum and 77 Combinations.

Every backtracking solution is choose → explore → un-choose. Line 7, the un-choose step, is the one people forget.

More backtracking