Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void getAllPerm(int item, int &r, vector<int> &boxes, int &count){
- // explore all the options/choose box for the current item
- /*
- n = 5, r = 3, item = 1
- _ _ _ _ _ (5 empty boxes present for item 1)
- So item 1 could explore/choose any of the box
- 1 _ _ _ _ , _ 1 _ _ _ , _ _ 1 _ _ , _ _ _ 1 _ , _ _ _ _ 1 [explore all these paths]
- Now at next level, we will make decision for item item 2
- If we are currently exploring the path where 1 _ _ _ _,
- So 2 would have 4 options as there are 4 different empty boxes where 2 could go
- 1 2 _ _ _ , 1 _ 2 _ _ , 1 _ _ 2 _ , 1 _ _ _ 2
- Repeat the same for the all the items available i.e. r
- This would generate all the perm, for example while exploring branch where _ 1 _ _ _ and currently at level 2
- The 4 options would be -
- 2 1 _ _ _ , _ 1 2 _ _ , _ 1 _ 2 _ , _ 1 _ _ 2
- The first option is a permutation of 1 2 _ _ _ [2 & 1 arranged themselves]
- */
- //base case
- if(item > r){
- // item > r; as when we would have made the decision/explored options for the last item, say 3, we would have called to 4
- count++;
- for(int i : boxes){
- cout << i;
- }
- cout << '\n';
- return;
- }
- for(int i = 0; i < boxes.size(); i++){
- // only choose those boxes which are empty because that's where the current item could go
- if(boxes[i] == 0){
- //place the item in the box such as to start generating perm like (1 _ _ _ _ ....)
- boxes[i] = item;
- // call the next level
- getAllPerm(item + 1, r, boxes, count);
- // backtrack the current option at the current state and choose other options as (_ 1 _ _ _ , _ _ 1 _ _ ...)
- boxes[i] = 0;
- }
- }
- }
- int main() {
- // your code goes here
- int n, r;
- cin >> n >> r;
- vector<int> boxes(n, 0);
- int count = 0;
- getAllPerm(1, r, boxes, count);
- cout << count << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
