Backtracking

INFO

It’s an Algorithm to permute string. Usefull to find all the possible permutations

EXAMPLE

Steps

• Create a function which take the string, the first index and the last index:
  • If start and end index are the same, end of the algorithm (print or return depends on what you wants)
  • Otherwise, loop on each index between start and end:
    • Swap string at index start and string at index i of loop
    • Call the function with as first index the first index + 1
    • Swap again string at index start and string at index i of loop

Code

#include <iostream>
#include <string>

void backtrack(std::string &s, int idx, int N) {
  if (idx == N)
    std::cout << s << std::endl;
  else {
    for (int i = idx; i <= N; i++) {
      std::swap(s[idx], s[i]);
      backtrack(s, idx + 1, N);
      // Reset
      std::swap(s[idx], s[i]);
    }
  }
}

int main(int ac, char *av[]) {
  std::string s = "ABC";
  int n = s.length();
  backtrack(s, 0, n - 1);
}

• ALGORITHM
• BACKTRACKING