Guidelines

If there is no way to linearly search for a solution (e.g. the path that goes through first 3 candidates, might get affected with a back edge coming from an element down the line e.g. 10th element) we have to default to exhaustive search (generate and test approach) using the tehnique called backtracking.

Most of the backtracking problem can be solved in this format:

• we defined the result list that will be passed to the helper function
• we define current position (in matrix, string...) and also the current result that we're producing (e.g. currentWord)
• we define the helper function where we will have our base case (e.g. index == word.length())) and then we do decision making defined by the problem statement and recursively call helper function (often while iterating over array)

Java

class Solution {
    public ResultType main(Input in) {
        ResultType result = new ResultType();
        helper(0, builder, in, result);
        return result;
    }

    private void helper(int index, Input builder, Input input, ResultType list){
        if(index == input.length()){
            list.add(new String(builder));
            return;
        }
        // selection take or don't take
        // we can also use loop if we have more than 2 options
        builder[index] = 'something';
        helper(index + 1, builder, input, list);
        builder[index] = '';
        helper(index + 1, builder, input, list);
    }
}

JavaScript

class ResultType {
  constructor() {
    this.list = [];
  }

  add(str) {
    this.list.push(str);
  }
}

function main(inObj) {
  const result = new ResultType();
  helper(0, [], inObj, result);
  return result;
}

function helper(index, builder, input, list) {
  if (index === input.length) {
    list.add(builder.join(""));
    return;
  }
  // selection take or don't take
  // we can also use a loop if we have more than 2 options
  builder[index] = "something";
  helper(index + 1, builder, input, list);
  builder[index] = "";
  helper(index + 1, builder, input, list);
}

Python

class ResultType:
    def __init__(self):
        self.list = []

    def add(self, string):
        self.list.append(string)

def main(inObj):
    result = ResultType()
    helper(0, [], inObj, result)
    return result

def helper(index, builder, input, result):
    if index == len(input):
        result.add(''.join(builder))
        return
    # selection take or don't take
    # we can also use a loop if we have more than 2 options
    builder[index] = 'something'
    helper(index + 1, builder, input, result)
    builder[index] = ''
    helper(index + 1, builder, input, result)

C++

class ResultType {
public:
    vector<string> list;

    void add(const string& str) {
        list.push_back(str);
    }
};

ResultType main(Input inObj) {
    ResultType result;
    helper(0, vector<char>(), inObj, result);
    return result;
}

void helper(int index, vector<char>& builder, const Input& input, ResultType& result) {
    if (index == input.length()) {
        result.add(string(builder.begin(), builder.end()));
        return;
    }
    // selection take or don't take
    // we can also use a loop if we have more than 2 options
    builder[index] = 'something';
    helper(index + 1, builder, input, result);
    builder[index] = '\0';
    helper(index + 1, builder, input, result);
}

If you want to skip duplicates in the result, sort the candidates/input array and while generation the solution check the following candidates[i-1] != candidates[i] if elements are different and if they're same check if we have used the previous candidate in the current partial solution only then you can pick the current element. There are 3 different arrangement you should remember:

• combinations choosing k elements out of n O(n!/((n-k)! * k!)) order is not importan in helper function we have for(int i = start; i <= n; ++i)
• permutations choosing all elements in different order O(n!) (once element is selected you have n-1 options to choose the next n * (n-1) * (n-2) ... = n!) in helper function we have for(int i = 0; i < nums.length; ++i)
• sets without loop pick or don't pick the element O(2^n) always remember binary represenation of number (110 can translate to first and second element being picked and third being omitted)

One important concept when it comes to backtracking is the concept of pruning the search. You can think of pruning just as escaping/saving the recursion calls early on based on some logic (solution out of boundary for example), determining early that partial solution cannnot converge the desired.