Introduction

Permutations means:

  • generating all possible arrangements
  • of array elements

Unlike subsets:

  • order matters

Example:

Input:1 2 3

Output:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Explanation:

Every arrangement of elements is generated.

This problem is one of the most important applications of:

Backtracking

Constraints

1 <= Array Size <= 8

Approach : Backtracking Solution

Explanations:

Explanation:

The idea is:

  • choose unused element
  • place it in current permutation

Steps:

  1. Start with empty permutation.
  2. Choose unused element.
  3. Add element.
  4. Recurse further.
  5. Backtrack and remove element.

This approach:

  • explores all arrangements
  • generates all permutations

Dry Run

Array:
1 2 3

Choose 1:
[1]

Choose 2:
[1,2]

Choose 3:
[1,2,3]

Backtrack:
[1,2]

Backtrack:
[1]

Continue remaining permutations...

Practice :

Complexity Analysis :

Time Complexity:- O(n!)
Explanation :
All possible permutations are generated.

Space Complexity:- O(n)
Explanation :
Recursion stack and permutation storage are used.

Why This Problem is Important

This problem builds the foundation for:

  • Backtracking
  • Recursion trees
  • Arrangement generation
  • Recursive exploration
  • State-space search

Real-World Applications

Permutation concepts are used in:

  • Password generation
  • Scheduling systems
  • Search algorithms
  • Game solving
  • Optimization problems

Common Beginner Mistakes

  • Forgetting backtracking step
  • Not tracking used elements
  • Duplicate permutations
  • Incorrect recursion condition
  • Modifying same array reference

Interview Tip

Interviewers often expect:

  • backtracking understanding
  • recursion tree explanation
  • used-array logic
  • complexity analysis

Always explain:

  • recursive exploration
  • backtracking step
  • permutation generation flow

Related Questions

  • Subsets
  • Combination Sum
  • N-Queens
  • Sudoku Solver
  • Backtracking Basics

Final Takeaway

The Permutations problem is one of the most important beginner backtracking problems.

It teaches:

  • backtracking
  • recursive exploration
  • state-space traversal
  • permutation generation

Understanding this problem builds a strong foundation for:

  • advanced backtracking problems
  • recursion optimization
  • interview-level algorithms.