Permutations et combinaisons
Énumérez toutes les permutations d’une liste, avec ou sans éléments en double, puis générez toutes les k-combinaisons et les variantes de somme de combinaisons.
Permutations et combinaisons est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Permutations et combinaisons
Les permutations sont des arrangements où l'ordre compte : [1,2,3] et [3,2,1] sont différents. Le nombre de permutations de n éléments est n!. Les combinaisons sont des sélections où l'ordre ne compte pas : choisir {1,2} revient au même que choisir {2,1}. Le nombre de combinaisons de k éléments parmi n est C(n,k) = n! / (k! × (n-k)!). Ces deux notions sont des schémas essentiels dans les problèmes d'entretien portant sur le comptage, l'énumération et la sélection.
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)Générer toutes les permutations
Utilisez un tableau booléen used pour suivre les éléments présents dans le chemin courant. À chaque étape, essayez chaque élément encore inutilisé. Après l'exploration, marquez à nouveau l'élément comme inutilisé. Contrairement aux sous-ensembles, il n'y a pas d'index start, car les permutations utilisent les éléments dans n'importe quel ordre. La récursion s'arrête lorsque 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]]Permutations par échange
Autre approche : échangez l'élément situé à la position start avec chaque élément de start à n-1, effectuez l'appel récursif, puis annulez l'échange. Cette méthode modifie le tableau sur place sans utiliser de tableau used. L'idée essentielle est qu'à chaque niveau, tout ce qui se trouve à gauche de start est fixé, et que vous choisissez l'élément à placer à la position start. Cette approche utilise légèrement moins de mémoire et constitue la base de l'algorithme de 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 orderPermutations II : gérer les doublons
Lorsque l'entrée contient des doublons (par exemple, [1, 1, 2]), l'approche fondée sur le tableau used génère des permutations en double. Pour corriger cela, triez le tableau, puis ignorez un doublon si l'élément identique précédent n'a pas été utilisé dans cet appel récursif. La condition est la suivante : if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. Cela garantit que les doublons sont toujours sélectionnés de gauche à droite.
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 6Permutation suivante (ordre lexicographique)
La permutation suivante (LeetCode 31) transforme un tableau sur place en sa prochaine permutation, immédiatement supérieure dans l'ordre lexicographique. Algorithme : (1) trouver l'index le plus à droite i tel que nums[i] < nums[i+1] ; (2) trouver l'index le plus à droite j tel que nums[j] > nums[i] ; (3) échanger nums[i] et nums[j] ; (4) inverser le suffixe situé après l'index i. Si aucun index i de ce type n'existe, inversez tout le tableau (on revient alors à la plus petite 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]Retour arrière pour les k-combinaisons
Générez toutes les combinaisons de k éléments parmi n (LeetCode 77). Utilisez un index de départ, comme pour les sous-ensembles, afin d'éviter de revisiter les éléments et de conserver l'ordre trié. Élaguez la recherche lorsqu'il reste moins de k - len(path) éléments : if len(nums) - i + 1 < k - len(path): break. Cela équivaut à l'approche précédente combine(n, k), mais en opérant sur un tableau réel.
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)) # 10Somme de combinaisons : réutilisation illimitée
La somme de combinaisons (LeetCode 39) autorise l'utilisation répétée de chaque nombre, sans limite. La différence avec les combinaisons standard est la suivante : au lieu de faire avancer start jusqu'à i+1, transmettez i (le même index) afin de pouvoir réutiliser l'élément courant. Pour l'élagage : si la cible restante devient égale à 0, enregistrez le chemin ; si elle devient négative, arrêtez-vous. Le tri permet de terminer plus tôt lorsque tous les candidats restants dépassent la cible restante.
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]]Somme de combinaisons II : sans réutilisation et avec doublons
La somme de combinaisons II (LeetCode 40) utilise chaque nombre au plus une fois, mais l'entrée peut contenir des doublons. Deux techniques sont combinées : faire avancer start jusqu'à i+1 (aucune réutilisation), et ignorer les doublons au même niveau (if i > start and nums[i] == nums[i-1]: continue) après le tri. Cette approche réunit la gestion des doublons des sous-ensembles II et la contrainte de non-réutilisation des combinaisons.
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]]Combinaisons de lettres d'un numéro de téléphone
Les combinaisons de lettres (LeetCode 17) associent chaque chiffre aux lettres correspondantes sur le clavier d'un téléphone et génèrent toutes les combinaisons de lettres possibles pour une chaîne de chiffres donnée. Il s'agit d'un problème de retour arrière dans lequel, à chaque position, nous choisissons une lettre parmi celles associées au chiffre, puis poursuivons la récursion. Pour une chaîne de longueur n comportant en moyenne k lettres par chiffre, la complexité temporelle est 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']Comparaison des permutations et des combinaisons
Différences structurelles essentielles : permutations — pas d'index de départ, utilisation d'un tableau used ou d'échanges pour éviter la réutilisation, n choix à chaque niveau de l'arbre et n! feuilles au total. Combinaisons — utilisation d'un index de départ pour imposer l'ordre, avec C(n,k) feuilles. Somme de combinaisons — pas d'avancement de start pour permettre la réutilisation, avec élagage selon la cible. Associer tout nouveau problème à l'une de ces trois formes vous donne immédiatement le bon modèle.
# 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}')Complexité et conseils pour les entretiens
La complexité temporelle de l'énumération est la suivante : permutations O(n × n!), combinaisons O(k × C(n,k)), somme de combinaisons O(n^(T/min_val)). L'espace utilisé est O(n) pour la profondeur de récursion, auquel s'ajoute O(output) pour les résultats. Conseils essentiels : (1) demandez toujours si l'ordre compte (permutation ou combinaison) ; (2) mentionnez la gestion des doublons avant qu'on vous le demande ; (3) énoncez toujours explicitement la condition d'élagage ; (4) pour de grandes valeurs de n, précisez que le résultat lui-même est exponentiel — l'algorithme est optimal pour cette tâche.
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)'Vérification rapide
Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : les permutations utilisent un tableau used et aucun index de départ, ce qui génère n! arrangements, les combinaisons utilisent un index de départ qui avance pour éviter la réutilisation, ce qui génère C(n,k) sélections, et les doublons dans ces deux problèmes sont gérés en triant les valeurs et en ignorant les valeurs répétées au même niveau de récursion. Nous allons maintenant appliquer le retour arrière au problème des N reines et explorer la propagation des contraintes.
Questions Fréquemment Posées
La leçon « Permutations et combinaisons » est-elle gratuite ?
Oui — le texte complet de « Permutations et combinaisons » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Permutations et combinaisons » ?
Énumérez toutes les permutations d’une liste, avec ou sans éléments en double, puis générez toutes les k-combinaisons et les variantes de somme de combinaisons. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Permutations et combinaisons » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modèle de retour sur trace : choisir, explorer, annuler
- Sous-ensembles et ensemble des parties
- Permutations et combinaisons
- Problème des N reines et propagation des contraintes