Introduction
Generating all permutations (orderings) or combinations (selections without regard to order) of a collection is one of the most common uses of backtracking. Both tasks share the same choose/explore/un-choose skeleton; they differ only in how candidates are chosen at each step -- permutations pick any unused element next, while combinations pick elements in increasing index order to avoid duplicate selections and enforce a fixed output size.
Cricket analogy: Listing every possible batting order for the top 4 is a permutation problem (order matters), while listing every possible pair of openers is a combination problem (order doesn't matter); both use the same choose-explore-unchoose search skeleton.
Approach/Syntax
def permutations(nums):
result = []
used = [False] * len(nums)
current = []
def backtrack():
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
current.append(nums[i]) # choose
backtrack() # explore
current.pop() # un-choose
used[i] = False
backtrack()
return result
def combinations(nums, k):
result = []
current = []
def backtrack(start):
if len(current) == k:
result.append(current[:])
return
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1) # explore (no reuse of earlier indices)
current.pop() # un-choose
backtrack(0)
return result
Explanation
In permutations, a used boolean array prevents an element from being picked twice within the same arrangement; every unused index is a valid next choice, so the branching factor at depth d is (n - d), giving n! total leaves. In combinations, the start parameter enforces that each recursive call only considers indices from start onward, which guarantees elements are chosen in increasing index order -- this is what avoids generating the same combination multiple times in different orders (e.g. [1,2] and [2,1] would otherwise both appear). The base case differs too: permutations stop when current has used every element, while combinations stop as soon as current reaches the fixed target size k.
Cricket analogy: For batting-order permutations, a 'used' array prevents a batter appearing twice, so branching shrinks from 11 to 10 to 9 down the order giving 11! total orders; for choosing 4 fielders for a slip cordon, a start index prevents picking the same pair in reverse, stopping once 4 are chosen.
Example
nums = [1, 2, 3]
print("Permutations of", nums)
for p in permutations(nums):
print(p)
print("\nCombinations of size 2 from", nums)
for c in combinations(nums, 2):
print(c)
Output
Permutations of [1, 2, 3] produce all 3! = 6 orderings: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Combinations of size 2 produce C(3,2) = 3 selections: [1,2], [1,3], [2,3]. Time complexity for permutations is O(n * n!) since there are n! results each of length n to copy into the output; for combinations of size k from n elements it is O(k * C(n, k)) for the same reason. Both use O(n) auxiliary space for the recursion stack and current buffer, excluding the space needed to store all output results.
Cricket analogy: Batting orders of 3 openers produce 3!=6 sequences, while choosing 2 of those 3 for a specific opening stand produces C(3,2)=3 pairs; generating all orders costs O(n*n!) since each of n! results has length n to copy, and choosing k of n costs O(k*C(n,k)).
Key Takeaways
- Permutations and combinations both use the choose/explore/un-choose backtracking template.
- Permutations track used elements with a boolean array and allow any unused index next, yielding n! results.
- Combinations use a start index to enforce increasing order and avoid duplicate selections, yielding C(n, k) results.
- The base case for permutations is 'current is full length n'; for combinations it is 'current has size k'.
- Time complexity is O(n * n!) for permutations and O(k * C(n, k)) for combinations, dominated by copying output.
Practice what you learned
1. What mechanism prevents an element from being reused within a single permutation in the backtracking permutations() function?
2. In the combinations() function, why does the recursive call use backtrack(i + 1) instead of backtrack(0)?
3. How many total permutations does permutations([1,2,3,4]) generate?
4. What is the base case (termination condition) for the combinations(nums, k) backtracking function?
Was this page helpful?
You May Also Like
The Backtracking Paradigm
Learn how backtracking systematically builds candidate solutions and abandons paths that cannot possibly succeed.
N-Queens Problem
Place N queens on an N×N chessboard so none attack each other, using backtracking with column, diagonal pruning.
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.