Practice › Recursion & Backtracking
Permutations of a String
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Zoho, TCS, Infosys
The string has distinct characters. Print all its permutations in lexicographic order.
Input
One string s.
Output
Each permutation on its own line.
Constraints
- 1 ≤ |s| ≤ 7
- All characters are distinct lowercase letters
Example 1
Input
abc
Output
abc acb bac bca cab cba
Example 2
Input
a
Output
a
Hints
- Sort the characters first so you start from the smallest permutation.
- Backtrack: at each position try every unused character in increasing order, mark it used, recurse, then unmark it.
Approach
Sort s. go(cur): if cur has all n characters, print it. Otherwise, for each unused character in sorted order, append it, mark it used, recurse, then undo both. Picking characters in increasing order at every level makes the output come out in lexicographic order. (C++'s next_permutation does the same job.) There are n! results, 5040 for n = 7.
Complexity: O(n! · n) time · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
string s, cur;
vector<bool> used;
void go() {
if (cur.size() == s.size()) {
cout << cur << "\n";
return;
}
for (size_t i = 0; i < s.size(); i++) {
if (used[i]) continue;
used[i] = true;
cur.push_back(s[i]);
go();
cur.pop_back();
used[i] = false;
}
}
int main() {
cin >> s;
sort(s.begin(), s.end());
used.assign(s.size(), false);
go();
return 0;
}Python solution
s = sorted(input().strip())
out = []
used = [False] * len(s)
def go(cur):
if len(cur) == len(s):
out.append("".join(cur))
return
for i, ch in enumerate(s):
if used[i]:
continue
used[i] = True
cur.append(ch)
go(cur)
cur.pop()
used[i] = False
go([])
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static char[] s;
static boolean[] used;
static StringBuilder cur = new StringBuilder(), out = new StringBuilder();
static void go() {
if (cur.length() == s.length) {
out.append(cur).append('\n');
return;
}
for (int i = 0; i < s.length; i++) {
if (used[i]) continue;
used[i] = true;
cur.append(s[i]);
go();
cur.deleteCharAt(cur.length() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s = sc.next().toCharArray();
Arrays.sort(s);
used = new boolean[s.length];
go();
System.out.print(out);
}
}Solve Permutations of a String online · All practice problems