# Backtracking

Addressing problems involves constructing a solution gradually, assembling it piece by piece, while eliminating those solutions that do not meet the specified constraints of the problem at hand.

Typical inquiries exploring the concept of backtracking encompass various well-known problems such as the N-queens problem, the Sum of Subsets problem, Graph Colouring, and Hamiltonian cycles. Here’s an example implementation of Backtracking:

pseudocode: Backtracking

--------------------------------------------------------------
Algorithm: Backtracking
--------------------------------------------------------------

1. Backtrack(x)
2.
3.     if x is not a solution
4.
5.         return false
6.
7.     if is a new solution
8.
9.         add to the list of solution
10.
11.    backtrack(expand x)
______________________________________________________________


C++

// C++ Program to Array Permutations
#include <iostream>
#include <vector>
#include <algorithm>

void solve(std::vector<int>& nums, int index, std::vector<std::vector<int>>& ans) {
// If index is equal to size of num then store our num vector in ans and return
if(index >= nums.size()) {
ans.push_back(nums);
return;
}

// Looping from index till size of the array
for(int i = index; i < nums.size(); i++) {
// Swap the ind and ith numbers in nums array
std::swap(nums[index], nums[i]);
// Recursive Call with increase in the index
solve(nums, index + 1, ans);
// backtracking
std::swap(nums[index], nums[i]);
}
}

std::vector<std::vector<int>> arrayPermutations(std::vector<int>& nums) {
// Initializing answer vector where we store permutations
std::vector<std::vector<int>> ans;
int index = 0;   // index of the starting point

// Function Call
solve(nums, index, ans);

return ans;
}

int main() {
// Initializing array
std::vector<int> arr = {1, 2, 3, 4};

// Function Call
std::vector<std::vector<int>> permutations = arrayPermutations(arr);
// Printing the permutations of vector arr
std::cout << "Permutations of {1, 2, 3, 4} are: " << std::endl;
for(int i = 0; i < permutations.size(); i++) {
std::cout << " [ ";
for(int j = 0; j < permutations[i].size(); j++) {
std::cout << permutations[i][j] << " ";
}
if(i != permutations.size() - 1) std::cout << "] ,";
}
std::cout << "]";
return 0;
}


References:

Previous
Next