Permutations and Combinations
Enumerate all permutations of a list with and without duplicate elements, and generate all k-combinations and combination-sum variants.
Permutations vs Combinations
Permutations are arrangements where order matters: [1,2,3] and [3,2,1] are different. The number of permutations of n items is n!. Combinations are selections where order does not matter: choosing {1,2} is the same as {2,1}. The number of k-combinations from n items is C(n,k) = n! / (k! × (n-k)!). Both are essential patterns in interview problems about counting, enumerating, and selecting.
import math
# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24
# Combinations
for k in range(n+1):
print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)Generating All Permutations
Use a used boolean array to track which elements are in the current path. At each step, try every unused element. After exploring, mark the element as unused again. Unlike subsets, there is no start index because permutations use elements in any order. The recursion bottoms out when len(path) == n.
def permutations(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True # CHOOSE
path.append(num)
backtrack(path) # EXPLORE
path.pop() # UNCHOOSE
used[i] = False
backtrack([])
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]All lessons in this course
- Backtracking Template: Choose, Explore, Unchoose
- Subsets and Power Set
- Permutations and Combinations
- N-Queens and Constraint Propagation