The guide to Backtracking — Selection Problems (Part 1)

By the end of this article series, you will be armed with crystal clear concepts of several selection problems solved with Backtracking.

I am writing this article assuming the reader has a basic knowledge of what is Recursion and Backtracking, if not I suggest you do it before moving on.

Types of Selection Problems

• Subsets are zero or more elements from a group of elements.

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

• Combinations are ways you can choose exactly K elements from a group of elements.

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

• Permutations are ways you can order a group of elements.

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 two main concepts that we are gonna use here are — Recursion and Backtracking. So, I will first share the “Brahmastras(a weapon)” tot tackle these two :

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:

(a)Make it and explore recursively. Pass the information for a choice to the next recursive call(s).

(b)Undo it after exploring. Restore everything to the way it was before making this choice.

3. Find our base case(s). What should we do when we are out of decisions?

Next, we will solve a few problems related to subsets, Combinations, and Permutations in the coming articles of this series.