You are given an N X N empty board. You have to place N objects in N different places on the board and have to print all the possible combinations for placing these N objects on the board. To show placed position, you can print 'P' at that position, and for empty space, you can print. ''.In this manner, Print all unique combinations.
Example 1
Input
N = 3
Output
First combination
P P P
. . .
. . .
Second combination
P P .
P . .
. . .
Third combination
P P .
. P .
. . .
Fourth combination
. P .
P . .
. P .
.
.
.
.
.
The nth combination
. . P
. . .
P P .
Explanation
So there are total N*N places where we can fit N objects, so we have to choose N places to place an object from N*N places means total combination will be (N*N)C(N) using the combination formula of nCr where we have to choose r objects from n objects.
Here, N*N = 9, N=3 so total possible combinations are 9C3 i.e
(9!) / ((3!) * (9 - 3)!) = 84
Approach
This problem can be solved by using recursion to generate all possible solutions. Make two recursive calls, one by placing an object at a particular position and one call without placing the object at that position. After placing an object at a position, increase the count of ‘objectplaced’. In the base case Print all unique combinations.
Algorithm
Create a 'printAllCombinations' function that will create all feasible solutions and will Print all unique combinations.
It will take as arguments an integer objectsPlaced indicating the total number of pieces placed, an integer N indicating the number of pieces required, two integers rowNo and 'colNo' indicating the row and column where the current piece will be placed, and a string combination indicating the matrix where pieces are placed.
The first call to 'printAllCombinations' will now take 0 for 'objectPlaced', N, 0, and 0 for rowNo and 'colNo', and an empty string for combination.
In every call, first check the base case that is If the rowNo is increased to N and all objects are placed, objectPlaced=N. Then print the answers and send them back. Otherwise, if 'objectPlaced' is not N, simply exit this call.
Make two calls now: one to add a 'P' to the current position, and another to leave that position and add a '.'.
At last, recursion will do all its tasks and will print all the possible combinations.
Code:
#include <bits/stdc++.h>
using namespace std;
// Count of total possible combinations
static int totalCombinations = 0;
// Function to Print all unique combinations
void printAllCombinations(int objectsPlaced, int N, int rowNo,int colNo, string combination)
{
// After reaching at last row of the box
if (rowNo == N) {
// If all the objects are placed print the box
if (objectsPlaced == N) {
//print the box
cout << combination <<endl <<endl;
// Increment the value of the combination
totalCombinations++;
}
return;
}
// Declaring current column and current row number
int nor = 0;
int noc = 0;
// This string will mark the place as marked
string x = "";
// This string will leave the place empty
string y = "";
// Increase current row number If the current column goes out of bound
if (colNo == N - 1) {
nor = rowNo + 1;
noc = 0;
x = combination + "P\n";
y = combination + ".\n";
}
// Otherwise simply increase the column number
else {
nor = rowNo;
noc = colNo + 1;
x = combination + "P\t";
y = combination + ".\t";
}
// Mark the position placed and explore all other paths
printAllCombinations(objectsPlaced + 1, N, nor, noc, x);
// Mark the position empty and explore all other paths
printAllCombinations(objectsPlaced, N, nor, noc, y);
}
int main()
{
// Input size of the board
int N = 2;
// Function call to Print all unique combinations
printAllCombinations(0, N, 0, 0, "");
// Total combinations
cout<<"Total Possible combinations : "<<totalCombinations;
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity to Print all unique combinations of setting N objects on an NxN board is O(2 ^ X), where X=N*N. There are total (N*N) positions on the board where we can place the object. For every place on the board, we have two choices, either to place the object or not so total for the N*N position. There are two choices. Recursion will explore all the paths; hence the time complexity to explore all the paths will be 2^(totalpositionns) and here, totalpositions in the board is N*N.
Space Complexity
O(1)
The space complexity to Print all unique combinations of setting N objects on an NxN board is O(1) since we are not using any extra space during the entire implementation, so this approach will use constant extra space.
FAQs
How is recursion different from backtracking? In recursion, the function calls itself until it reaches a base case. We use recursion in backtracking to investigate all of the possibilities until we find the optimal solution to the problem.
How was the base case condition formed in this problem? Base condition is the point where recursion call end is about to end, so in this approach, when the current row number reaches to last means, we have explored all rows. After this, we have to check whether we have placed all N objects. If yes, print the string.
Key Takeaways
In this blog, we discussed the solution to Print all unique combinations of setting N objects on an NxN board. Along with the solution, we also explored the time and space complexity of the solution.
If you want to learn more about Recursion and Backtracking and want to practice some questions which require you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.