Leetcode List : https://leetcode.com/list/5v3kl3d1

Here is a list of backtracking problems that can be useful to practice to solve more problems during interview / contest. Backtracking algorithm is straightforward, but when it comes to real problems sometimes it is not obvious how we should tweak the algorithm.

Let's check the basic description and template of backtracking algorithm:

Wikipedia definition: Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

void dfs(arguments) {
	if (condition == true) { // Condition when we should stop our exploration.
		result.push_back(current);
		return;
	}
	for (int i = num; i <= last; i++) {
		current.push_back(i); // Explore candidate.
		dfs(arguments);
		current.pop_back();   // Abandon candidate.
	}
}

One thing to remember before we can jump to some backtracking problems:

1. Permutation: can be thought of number of ways to order some input.
   • Example: permutations of ABCD, taken 3 at a time (24 variants): ABC, ACB, BAC, BCA, ...
2. Combnation: can be thought as the number of ways of selecting from some input.
   • Example: combination of ABCD, taken 3 at a time (4 variants): ABC, ABD, ACD, and BCD.
3. Subset: can be thought as a selection of objects form the original set.
   • Example: subset of ABCD: 'A', 'B', 'C', 'D,' 'A,B' , 'A,C', 'A,D', 'B,C', 'B,D', 'C,D', 'A,B,C', ...

From now let's start to apply this algorithm to solve some backtracking problems.

• Permutations: this set of problems related to generating (subset of) all possible permutations. Let's have a look at fist problem: Permutations In this problem we should return ALL the possible permutations from DISTINCT integer array.

• Another variation of the problem is Permutations II. The only difference between first problem is that we MAY have DUPLICATES in the input array.

• Combinations: we are given two integers n and k, return ALL possible combinations of k numbers out of the range [1, n]. If you want to solve this problem before jumping to the solution, here is the link: Combinations

• Let's next check another example: Combination Sum II. This time instead of using hash table we will sort th elements before invoking dfs() for the first time. We are given a collection of candidates and a target number, find ALL UNIQUE combinations in candidates where the candidate numbers sum to target.