# 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 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 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:

--

--

## More from Manvi Tyagi

Software Developer working to become a better Software Developer everyday :)

Love podcasts or audiobooks? Learn on the go with our new app.

## Manvi Tyagi

Software Developer working to become a better Software Developer everyday :)