C++ Program to Find All Permutations of String with Explanation
C++
Hard
Strings
37 views
1 min read
198 words
This problem helps you practice core C++ fundamentals in a practical way. It builds intuition around all, arrangement, character. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Generate all possible arrangements of string characters.
Real Life: Password combinations, cryptography.
Input Format
A string S.
Output Format
All possible arrangements (permutations) of the string characters.
Each arrangement printed on a new line.
Constraints
• Length of string ≥ 1
• Characters may be unique
• Use recursion or built-in logic
Concept Explanation
An arrangement (permutation) means changing the order of characters.
All possible orders are generated.
This is useful in password generation and cryptography.
Step-by-Step Logic
1.Take input string S.
2.Fix one character at a time at the first position.
3.Swap the fixed character with each position one by one.
4.Recursively generate permutations for the remaining part of the string.
5.When the index reaches the last character:
• Print the current string.
6.After recursion, swap characters back to restore original order
(this is called backtracking).
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
void generatePermutations(string str, int left, int right) {
if(left == right) {
cout << str << endl;
} else {
for(int i = left; i <= right; i++) {
// Swap
char temp = str[left];
str[left] = str[i];
str[i] = temp;
// Recurse
generatePermutations(str, left + 1, right);
// Backtrack
temp = str[left];
str[left] = str[i];
str[i] = temp;
}
}
}
void string_q15_permutations() {
string text = "ABC";
cout << "All permutations of " << text << ":" << endl;
generatePermutations(text, 0, text.length() - 1);
}
Output Example
Output:
ABC
ACB
BAC
BCA
CAB
CBA
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Generate all possible arrangements of string characters.
Real Life: Password combinations, cryptography.
Input / Output
Output
All possible arrangements (permutations) of the string characters.
Each arrangement printed on a new line.
Constraints
• Length of string ≥ 1
• Characters may be unique
• Use recursion or built-in logic
Examples
Output:
ABC
ACB
BAC
BCA
CAB
CBA
Explanation
Concept Explanation
An arrangement (permutation) means changing the order of characters.
All possible orders are generated.
This is useful in password generation and cryptography.
Step-by-Step Explanation
1.Take input string S.
2.Fix one character at a time at the first position.
3.Swap the fixed character with each position one by one.
4.Recursively generate permutations for the remaining part of the string.
5.When the index reaches the last character:
• Print the current string.
6.After recursion, swap characters back to restore original order
(this is called backtracking).
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
void generatePermutations(string str, int left, int right) {
if(left == right) {
cout << str << endl;
} else {
for(int i = left; i <= right; i++) {
// Swap
char temp = str[left];
str[left] = str[i];
str[i] = temp;
// Recurse
generatePermutations(str, left + 1, right);
// Backtrack
temp = str[left];
str[left] = str[i];
str[i] = temp;
}
}
}
void string_q15_permutations() {
string text = "ABC";
cout << "All permutations of " << text << ":" << endl;
generatePermutations(text, 0, text.length() - 1);
}
Solutions (0)
No solutions submitted yet. Be the first!
