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