The guide to Backtracking — Selection Problems (Part 1)

Input:  S = {1, 2, 2}
Output: {}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}

Explanation:
The total subsets of given set are -
{}, {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2}, {1, 2, 2}
Here {2} and {1, 2} are repeated twice so they are considered
only once in the output
Input: int arr[] = {1, 2, 3, 4, 5}Output:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Input: a[] = {1, 2, 3}
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

The Recursion Brahmastra :

  1. Find what information we need to keep track of. What inputs/outputs are needed to solve the problem at each step? Do we need a wrapper function?
  2. Find our base case(s). What are the simplest (nonrecursive) instance(s) of this problem?
  3. Find our recursive step. How can this problem be solved in terms of one or more simpler instances of the same problem that leads to a base case?
  4. Ensure every input is handled. Do we cover all possible cases? Do we need to handle errors?

The Backtracking Brahmastra :

  1. Find what choice(s) we have at each step. What different options are there for the next step?
  2. For each valid choice:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store