Introduction

A permutation of an array is any arrangement of its elements in a different order. In coding problems, the real question is usually not the definition but how to generate permutations efficiently and how to avoid duplicate output when the array contains repeated values.

Understand the Growth Rate

If an array has n distinct elements, it has n! permutations.

For example:

• '3 elements produce 6 permutations'
• '4 elements produce 24'
• '5 elements produce 120'

This grows very quickly, so permutation generation is inherently expensive for larger arrays. That is not a flaw in the algorithm; it is the nature of the problem.

Generate Permutations with Backtracking

A standard approach is recursive backtracking with swaps.

1def permute(nums):
2    result = []
3
4    def backtrack(start):
5        if start == len(nums):
6            result.append(nums[:])
7            return
8
9        for i in range(start, len(nums)):
10            nums[start], nums[i] = nums[i], nums[start]
11            backtrack(start + 1)
12            nums[start], nums[i] = nums[i], nums[start]
13
14    backtrack(0)
15    return result
16
17print(permute([1, 2, 3]))

This works by fixing one position at a time and recursively permuting the remaining suffix.

Avoid Duplicate Permutations When Values Repeat

If the array contains repeated values, naive backtracking can emit duplicate permutations. A common fix is to sort first and skip repeated choices at each depth.

1def permute_unique(nums):
2    nums.sort()
3    result = []
4    used = [False] * len(nums)
5
6    def backtrack(path):
7        if len(path) == len(nums):
8            result.append(path[:])
9            return
10
11        for i in range(len(nums)):
12            if used[i]:
13                continue
14            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
15                continue
16
17            used[i] = True
18            path.append(nums[i])
19            backtrack(path)
20            path.pop()
21            used[i] = False
22
23    backtrack([])
24    return result

That is the right pattern when the task is “unique permutations” rather than “all index permutations.”

Use a Library When the Language Provides One

If the goal is simply to iterate permutations rather than implement the algorithm yourself, a library function is often clearer.

1from itertools import permutations
2
3for p in permutations([1, 2, 3]):
4    print(p)

This is concise and reliable, but it does not change the factorial cost.

Materialize or Stream Based on the Goal

Some code wants a complete list of permutations. Other code only wants to process them one at a time. If you only need iteration, prefer a generator or streaming approach because it avoids storing all permutations in memory at once.

That distinction does not fix the time complexity, but it can greatly improve memory behavior.

Decide Whether You Need All Permutations

Many problems that mention permutations do not actually require materializing all of them. Sometimes you need:

• only the next lexicographic permutation
• the count of permutations
• one valid permutation under constraints
• the best permutation under a scoring rule

If that is the real task, generating all permutations may be unnecessary and too expensive.

Common Pitfalls

• Forgetting that permutation generation grows factorially and becomes infeasible quickly.
• Returning the same array reference repeatedly instead of copying the current state.
• Generating duplicate permutations when the input contains repeated values.
• Using recursion without understanding the backtracking undo step.
• Enumerating all permutations when the real problem needs only one or a count.

Summary

• A permutation is a reordering of array elements.
• Backtracking with swaps is a standard way to generate permutations.
• Inputs with duplicates require extra logic to avoid repeated results.
• Library helpers such as itertools.permutations are great when implementation details do not matter.
• Always check whether you really need all permutations before generating them.