Permutation Sequence














































Permutation Sequence



The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Format for Input:-

  1. n representing the number , k representing kth sequence

The above input method will be clear from the below code.

Format for Output:-

  • Return the string.

So, let's see the code and how it is implemented.

#include<bits/stdc++.h>

using namespace std;

class Solution {
public:
int N,target,ct;
string req;
vector<char>ch;
vector<bool>vis;
bool permute(int totsz){
bool flag=false;
for(int i=1;i<=N;i++){
if(totsz+1<N&&vis[i]==false){
vis[i]=true;
flag=permute(totsz+1);
if(flag){
ch.push_back(i+'0');
return true;
}
vis[i]=false;
}
else if(totsz+1==N&&vis[i]==false){
ct++;
if(ct==target){
ch.push_back(i+'0');
return true;
}
}
}
return false;
}
string getPermutation(int n, int k) {
N=n;
target=k;
ct=0;
vector<bool>visited(n+1,false);
vis=visited;
permute(0);
vector<char>z=ch;
string st="";
for(auto it:z)st+=it;
reverse(st.begin(),st.end());
return st;
}
};

int stringToInteger(string input) {
return stoi(input);
}

int main() {
string line;
while (getline(cin, line)) {
int n = stringToInteger(line);
getline(cin, line);
int k = stringToInteger(line);
string ret = Solution().getPermutation(n, k);

string out = (ret);
cout << out << endl;
}
return 0;
}


Example 1:

Input: n = 3, k = 3
Output: "213"

The sample inputs and outputs are given below:-
Input: n = 4, k = 9
Output: "2314"

More Articles of Khitish Panigrahi:

Name Views Likes
Rotate Image 142 0
Edit Distance 88 1
Integer to Roman 117 2
Roman to Integer 107 2
Shortest Path Problem 111 2
Dijkstra 115 2
Hamiltonian Path 105 3
Travelling Salesman Problem 109 3
Hamiltonian Cycle 108 3
Number of Operations to Make Network Connected 104 2
Time Needed to Inform All Employees 101 2
Last Stone Weight II(any weight can be picked) 113 2
Last Stone Weight 119 2
Course Schedule II (print the order) 91 2
Course Schedule 103 2
0-1knapsack 116 2
Commutable Islands 224 2
Cheapest Flights Within K Stops 114 2
Friend Circles 99 2
Longest Palindromic Subsequence (Print Subsequence) 107 2
Longest Palindromic Subsequence (print only length) 98 2
longest palindromic substring(improved) 95 2
Longest Common Subsequence (Print the Subsequence) 98 2
Longest Common Subsequence (Print only Length) 100 2
Cycle in Undirected Graph 122 2
IOT SMART HOME 142 2
Working of Home Networks 100 2
Smart and Safe Cab Finder Algorithm 147 2
Minimum Falling Path Sum 174 3
Maximum Length of a Concatenated String with Unique Characters 100 3
Stack Pushing Game(Push Dominoes Game) 101 3
Boats to Save People 120 3
Find Single Non-repeated Number 96 3
Create Ranges 90 3
Triangle 95 3
Restore IP Addresses 100 4
Number of Matching Subsequences 89 3
Max Area of Island 101 3
Number of Islands 85 3
Is Subsequence 99 3
Word Break 98 3
Perfect Number 97 3
Longest Arithmetic Sequence 95 3
Container With Most Water 101 3
Maximal Square 95 3
Best Time to Buy and Sell Stock 100 3
Distance Between Bus Stops 97 3
Validate IP Address 110 3
Longest Mountain in Array 105 4
Sequential Digits 101 3
Path with Maximum Gold 112 3
House Robber with houses arranged in circular manner 127 3
Increasing Triplet Subsequence 110 5
4Sum 106 3
3Sum 97 3
ZigZag Conversion 133 4
House Robber 97 3
Minimum Path Sum 98 3
Unique Paths with obstacles 90 2
Find and Replace Pattern 100 3
Minimum Size Subarray Sum 97 3
Maximum Subarray 103 5
Find All Anagrams in a String 65 3
Permutation in String 66 3
Subarray Sum Equals K 102 3
Maximum Product Subarray 81 4
Permutation with duplicates 77 6
Subsets with duplicates 77 7
Partition Equal Subset Sum 69 5
Relative Sort Array 65 3
Permutations 67 4
Combination Sum 125 4
All combinations that add up to a given sum 69 3
Combinations 84 7
Palindrome Partitioning 70 3
Climbing Stairs 86 5
Fibonacci Number 83 5
Unique Paths 76 3
Longest Increasing Subsequence 66 8
Gas Station 75 7
Minimum number of Perfect square needed to form a number 60 7
Permutation Sequence 142 16
Coin Change 71 6
Multiple Word Searching Algorithm 78 8
Word Search 67 6
Valid Anagram 91 8
Remove Nth Node From End of List 90 6
Linked List Cycle 67 6
Implement strStr() 67 4
Odd Even Linked List 60 6
Valid Palindrome 64 4
Maximum Depth of Binary Tree 60 3
Binary Tree Zigzag Level Order Traversal 78 4
Kth Smallest Element in a BST 47 2
Evaluate Reverse Polish Notation 64 3
String to Integer (atoi) 82 4
Intersection of Two Linked Lists 69 3
Multiply Strings 70 5
Palindromic Substrings 59 4
Add Strings 56 2
Longest Substring Without Repeating Characters 63 4
Longest Palindromic Substring 62 2
Jump Game 68 3
Majority Element 59 2
Top K Frequent Elements 91 7
Factorial Trailing Zeroes 53 2
Excel Sheet Column Number 55 3
Find Peak Element 84 4
Merge Intervals 57 3
Letter Combinations of a Phone Number 69 4
Populating Next Right Pointers in Each Node 66 2
Invert Binary Tree 62 4
Swap Nodes in Pairs 60 5
3Sum Closest 56 2
Permutation Sequence 85 4
Letter Tile Possibilities 124 3
The k-th Lexicographical String of All Happy Strings of Length n 70 3
Children Sum Parent 129 5
Check if Binary Tree is BST 126 5
Delete Node in Linked List without a head pointer 96 2
Connect all siblings in a Binary Search Tree 86 2
Delete a node from BST in C++ 96 3

Comments