Permutations and Combinations
Enumerate all permutations of a list with and without duplicate elements, and generate all k-combinations and combination-sum variants.
Permutations and Combinations is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]]Swap-Based Permutations
An alternative: swap element at position start with each element from start to n-1, recurse, then swap back. This modifies the array in-place without a used array. The key insight is that at each level, everything to the left of start is fixed, and we choose which element to place at position start. This is slightly more memory-efficient and is the basis of Heap's algorithm.
def permutations_swap(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # CHOOSE (swap)
backtrack(start + 1) # EXPLORE
nums[start], nums[i] = nums[i], nums[start] # UNCHOOSE (swap back)
backtrack(0)
return result
print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different orderPermutations II: Handling Duplicates
When the input has duplicates (e.g., [1, 1, 2]), the used-array approach generates duplicate permutations. Fix: sort the array, then skip a duplicate if the previous identical element was not used in this recursive call. The condition: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. This enforces that duplicates are always chosen left-to-right.
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i in range(len(nums)):
if used[i]: continue
# Skip if this num is a duplicate and the previous dup was not used
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
print(permutations_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6Next Permutation (Lexicographic)
Next Permutation (LeetCode 31) transforms an array into its next lexicographically greater permutation in-place. Algorithm: (1) Find the rightmost index i where nums[i] < nums[i+1]. (2) Find the rightmost index j where nums[j] > nums[i]. (3) Swap nums[i] and nums[j]. (4) Reverse the suffix after index i. If no such i exists, reverse the whole array (wraps to smallest permutation).
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost i where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost j where nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix after i
nums[i+1:] = nums[i+1:][::-1]
return nums
print(next_permutation([1, 2, 3])) # [1,3,2]
print(next_permutation([3, 2, 1])) # [1,2,3] (wraps)
print(next_permutation([1, 1, 5])) # [1,5,1]k-Combinations Backtracking
Generate all combinations of k elements from n (LeetCode 77). Use a start index (like subsets) to avoid revisiting elements and maintain sorted order. Prune when fewer than k - len(path) elements remain: if len(nums) - i + 1 < k - len(path): break. This is equivalent to the earlier combine(n, k) but operating on an actual array.
def combinations(nums, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(nums)):
# Pruning: not enough elements left
if len(nums) - i < k - len(path):
break
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3)) # 10Combination Sum: Unlimited Reuse
Combination Sum (LeetCode 39) allows each number to be used unlimited times. The difference from standard combinations: instead of advancing start to i+1, pass i (same index) to allow reusing the current element. Pruning: if the remaining target becomes 0, record the path; if it goes negative, stop. Sorting enables early termination when all remaining candidates exceed the remaining target.
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # all remaining are too big
path.append(c)
backtrack(i, path, remaining - c) # reuse allowed: pass i, not i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]Combination Sum II: No Reuse, With Duplicates
Combination Sum II (LeetCode 40) uses each number at most once but the input may contain duplicates. The combination of two techniques: advance start to i+1 (no reuse), and skip duplicates at the same level (if i > start and nums[i] == nums[i-1]: continue) after sorting. This is the union of the duplicate-handling from subsets II and the no-reuse constraint from combinations.
def combination_sum_ii(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
# Skip duplicates at same level
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i]) # no reuse: i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]Letter Combinations of Phone Number
Letter Combinations (LeetCode 17) maps each digit to letters on a phone keypad and generates all possible letter combinations for a given digit string. This is a backtracking problem where at each position we choose one letter from the digit's mapping and recurse. For a string of length n with average k letters per digit, the time complexity is O(kⁿ).
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']Comparing Permutations and Combinations
Key structural differences: Permutations — no start index, use a used array or swap to avoid reuse, tree has n choices at each level, total n! leaves. Combinations — use a start index to enforce ordering, C(n,k) leaves. Combination Sum — no start advance for reuse, prune on target. Mapping any new problem to one of these three forms gives you the right template immediately.
# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)
# Quick reference:
import math
n = 5
print(f'Perm({n}) = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')Complexity and Interview Tips
Time complexity for enumeration: Permutations O(n × n!), Combinations O(k × C(n,k)), Combination Sum O(n^(T/min_val)). Space is O(n) for the recursion depth plus O(output) for results. Key tips: (1) Always clarify whether order matters (permutation vs combination). (2) Mention duplicate handling before being asked. (3) Always state the pruning condition explicitly. (4) For large n, note that output itself is exponential — the algorithm is optimal for the task.
import math
# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')
# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: permutations use a used-array and no start index, generating n! arrangements, combinations use a start index that advances to avoid reuse, generating C(n,k) selections, and duplicates in both problems are handled by sorting and skipping repeated values at the same recursion level. Next up we apply backtracking to the N-Queens problem and explore constraint propagation.
Frequently asked questions
Is the “Permutations and Combinations” lesson free?
Yes — the full text of “Permutations and Combinations” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Permutations and Combinations”?
Enumerate all permutations of a list with and without duplicate elements, and generate all k-combinations and combination-sum variants. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Permutations and Combinations” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Backtracking Template: Choose, Explore, Unchoose
- Subsets and Power Set
- Permutations and Combinations
- N-Queens and Constraint Propagation