DSA problem
Generate All Permutations of a String
Given a string S, generate all possible permutations of its characters and return them.
This is a classic backtracking problem and one of the most important recursion exercises. The idea: fix one character at a time, then recursively permute the remaining characters. For a string of length N there are N! permutations. At each level of recursion you try placing each remaining character at the current position; after exploring that branch you backtrack - undo the choice and try the next character.
This generate-explore-undo pattern is the essence of backtracking, used to solve Sudoku, N-Queens, combinatorial optimization, constraint satisfaction, and many graph problems. Handling duplicates (e.g. "aab" should not produce repeated permutations) is a common follow-up - use a set at each recursion level to skip characters already placed at that position.
Examples
S = "ABC"["ABC", "ACB", "BAC", "BCA", "CBA", "CAB"]S = "A"["A"]Constraints
- 1 <= |S| <= 8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.