Permutationen und Kombinationen
Enumerieren Sie alle Permutationen einer Liste mit und ohne doppelte Elemente und erzeugen Sie alle k-Kombinationen sowie Varianten der Kombinationssumme.
Permutationen und Kombinationen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Permutationen und Kombinationen
Permutationen sind Anordnungen, bei denen die Reihenfolge eine Rolle spielt: [1,2,3] und [3,2,1] sind verschieden. Die Anzahl der Permutationen von n Elementen beträgt n!. Kombinationen sind Auswahlen, bei denen die Reihenfolge keine Rolle spielt: Die Auswahl von {1,2} ist identisch mit {2,1}. Die Anzahl der k-Kombinationen aus n Elementen beträgt C(n,k) = n! / (k! × (n-k)!). Beide sind wichtige Muster bei Interviewaufgaben zum Zählen, Aufzählen und Auswählen.
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)Alle Permutationen erzeugen
Verwenden Sie ein boolesches Array used, um zu verfolgen, welche Elemente sich im aktuellen Pfad befinden. Probieren Sie bei jedem Schritt jedes noch nicht verwendete Element aus. Markieren Sie das Element nach der Erkundung wieder als nicht verwendet. Anders als bei Teilmengen gibt es keinen start-Index, da Permutationen Elemente in beliebiger Reihenfolge verwenden. Die Rekursion endet, wenn len(path) == n gilt.
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]]Permutationen durch Vertauschen
Eine Alternative besteht darin, das Element an der Position start mit jedem Element von start bis n-1 zu vertauschen, die Rekursion auszuführen und anschließend wieder zurückzutauschen. Dadurch wird das Array direkt verändert, ohne ein used-Array zu benötigen. Die entscheidende Erkenntnis ist, dass auf jeder Ebene alles links von start feststeht und Sie auswählen, welches Element an die Position start gesetzt wird. Dieser Ansatz benötigt etwas weniger Speicher und bildet die Grundlage für den Algorithmus von Heap.
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 orderPermutationen II: Duplikate behandeln
Wenn die Eingabe Duplikate enthält (z. B. [1, 1, 2]), erzeugt der Ansatz mit dem used-Array doppelte Permutationen. Die Lösung: Sortieren Sie das Array und überspringen Sie ein Duplikat, wenn das vorherige identische Element in diesem Rekursionsaufruf nicht verwendet wurde. Die Bedingung lautet: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. Dadurch wird erzwungen, dass Duplikate immer von links nach rechts ausgewählt werden.
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 6Nächste Permutation (lexikografisch)
Next Permutation (LeetCode 31) wandelt ein Array direkt in seine nächstgrößere Permutation in lexikografischer Reihenfolge um. Algorithmus: (1) Finden Sie den rechtesten Index i, für den nums[i] < nums[i+1] gilt. (2) Finden Sie den rechtesten Index j, für den nums[j] > nums[i] gilt. (3) Vertauschen Sie nums[i] und nums[j]. (4) Kehren Sie das Suffix nach dem Index i um. Wenn kein solches i existiert, kehren Sie das gesamte Array um (dadurch wird zur kleinsten Permutation gewechselt).
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]Backtracking für k-Kombinationen
Erzeugen Sie alle Kombinationen aus k Elementen von n Elementen (LeetCode 77). Verwenden Sie wie bei Teilmengen einen Startindex, um bereits besuchte Elemente nicht erneut zu betrachten und die sortierte Reihenfolge beizubehalten. Brechen Sie ab, wenn weniger als k - len(path) Elemente übrig sind: if len(nums) - i + 1 < k - len(path): break. Dies entspricht dem zuvor verwendeten combine(n, k), arbeitet jedoch mit einem tatsächlichen 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: Unbegrenzte Wiederverwendung
Combination Sum (LeetCode 39) erlaubt, jede Zahl unbegrenzt oft zu verwenden. Der Unterschied zu normalen Kombinationen: Anstatt i+1 als neuen Startindex zu übergeben, übergeben Sie i (denselben Index), damit das aktuelle Element erneut verwendet werden kann. Beim Abschneiden gilt: Wenn das verbleibende Ziel 0 ergibt, speichern Sie den Pfad; wird es negativ, brechen Sie ab. Durch Sortieren können Sie vorzeitig abbrechen, sobald alle verbleibenden Kandidaten größer als das verbleibende Ziel sind.
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: Keine Wiederverwendung, mit Duplikaten
Combination Sum II (LeetCode 40) verwendet jede Zahl höchstens einmal, wobei die Eingabe Duplikate enthalten kann. Dazu werden zwei Techniken kombiniert: Erhöhen Sie start auf i+1 (keine Wiederverwendung) und überspringen Sie Duplikate auf derselben Ebene (if i > start and nums[i] == nums[i-1]: continue), nachdem Sie sortiert haben. Dies verbindet die Behandlung von Duplikaten aus Subsets II mit der Einschränkung ohne Wiederverwendung aus den Kombinationen.
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]]Buchstabenkombinationen einer Telefonnummer
Letter Combinations (LeetCode 17) ordnet jeder Ziffer die Buchstaben einer Telefontastatur zu und erzeugt alle möglichen Buchstabenkombinationen für eine gegebene Ziffernfolge. Dies ist ein Backtracking-Problem, bei dem an jeder Position ein Buchstabe aus der Zuordnung der Ziffer ausgewählt und anschließend die Rekursion fortgesetzt wird. Für eine Zeichenfolge der Länge n mit durchschnittlich k Buchstaben pro Ziffer beträgt die Zeitkomplexität 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']Permutationen und Kombinationen im Vergleich
Die wichtigsten strukturellen Unterschiede: Permutationen — kein Startindex, ein used-Array oder Vertauschen verhindert die Wiederverwendung, der Baum hat auf jeder Ebene n Auswahlmöglichkeiten und insgesamt n! Blätter. Kombinationen — ein Startindex erzwingt die Reihenfolge, es gibt C(n,k) Blätter. Combination Sum — der Startindex wird zur Wiederverwendung nicht erhöht, stattdessen wird anhand des Zielwerts abgeschnitten. Wenn Sie ein neues Problem einer dieser drei Formen zuordnen, erhalten Sie sofort das passende Muster.
# 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}')Komplexität und Tipps für Interviews
Die Zeitkomplexität für die Aufzählung beträgt: Permutationen O(n × n!), Kombinationen O(k × C(n,k)), Combination Sum O(n^(T/min_val)). Der Speicherbedarf beträgt O(n) für die Rekursionstiefe zuzüglich O(Ausgabe) für die Ergebnisse. Wichtige Tipps: (1) Klären Sie immer, ob die Reihenfolge eine Rolle spielt (Permutation oder Kombination). (2) Erwähnen Sie die Behandlung von Duplikaten, bevor Sie danach gefragt werden. (3) Geben Sie die Bedingung zum Abschneiden immer ausdrücklich an. (4) Weisen Sie bei großen n darauf hin, dass bereits die Ausgabe exponentiell groß ist — der Algorithmus ist für diese Aufgabe optimal.
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)'Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Permutationen verwenden ein used-Array und keinen Startindex und erzeugen n! Anordnungen, Kombinationen verwenden einen Startindex, der zur Vermeidung von Wiederverwendung erhöht wird, und erzeugen C(n,k) Auswahlen und Duplikate werden bei beiden Problemen durch Sortieren und das Überspringen wiederholter Werte auf derselben Rekursionsebene behandelt. Als Nächstes wenden wir Backtracking auf das N-Queens-Problem an und untersuchen Constraint Propagation.
Häufig gestellte Fragen
Ist die Lektion „Permutationen und Kombinationen“ kostenlos?
Ja — der vollständige Text von „Permutationen und Kombinationen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Permutationen und Kombinationen“?
Enumerieren Sie alle Permutationen einer Liste mit und ohne doppelte Elemente und erzeugen Sie alle k-Kombinationen sowie Varianten der Kombinationssumme. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Permutationen und Kombinationen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Backtracking-Schema: Auswählen, Erkunden, Auswahl zurücknehmen
- Teilmengen und Potenzmenge
- Permutationen und Kombinationen
- N-Damen und Constraint Propagation