Backtracking problems made easy

Backtracking problems seems to be one of the tricky part while studying DSA. But once we figure out a pattern in it, then its even easier than array problems.

A general code structure of a backtracking problem solution looks like :

    void Backtrack(int start, vector<int>&arr, int &ans)
    {
        //Base case 
    
        for(int i=start; i<arr.size(); i++)
        {
            //include the current element at this position if possible in the ans 
            
            Backtrack(start+1) // here take care whethere to pass start or start+1 dending on the usecase
            
            //backtrack by removing current element 
        }
    }

To avoid duplicates in backtracking, we generally sort the array/list, then keep track of the duplicates by arr[i] == arr[i-1].

Here are some good backtracking problems which makes our understanding about the topic more firm :

1. Letter Combinations of a Phone Number
2. Generate Parentheses
3. Sudoku Solver
4. Combination Sum
5. Combination Sum II
6. Permutations
7. Permutations II
8. N-Queens
9. Combinations
10. Subsets
11. Subsets II
12. Restore IP Addresses
13. Palindrome Partitioning
14. Word Break
15. Combination Sum III
16. Target Sum
17. Letter Case Permutation