# 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:intarr[] = {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 :*

*The Recursion Brahmastra :*

**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?**Find our base case(s)**. What are the simplest (nonrecursive) instance(s) of this problem?**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?**Ensure every input is handled.**Do we cover all possible cases? Do we need to handle errors?

## The Backtracking Brahmastra :

**Find what choice(s) we have at each step.**What different options are there for the next step?**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.