Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

abc

Output

abc
acb
bac
bca
cab
cba

Example 2

Input

a

Output

a

Hints

  1. Sort the characters first so you start from the smallest permutation.
  2. 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