Backtracking

---

Keywords

recursive, O(n!/(n−m)!)

---

Variables

1. visited[] : Keep track of numbers used in current sequence.
2. int depth
3. arr[] : Stores the sequence being constructed.

Stages

1. If a number is not used, mark it as used (visited[]).
2. Store it in arr[], then call dfs() recursively.
3. After running, backtrack by marking the number as unused (visited[]).

Code

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX]={0,};
bool visited[MAX]={0, };

void dfs(int depth){
  if(depth == m){
    for(int i = 0; i < m; i++){
      cout << arr[i] << " ";
    }
    cout<<"\n";
    return;
  }
  for(int i= 1; i <= n; i ++){
    if(!visited[i]){
      visited[i] = true;
      arr[depth] = i;
      dfs(depth+1);
      visited[i] = false;
    }
  }
}

int main() {
  cin>>n>>m;
  dfs(0);
}

Step-by-Step Execution