順列と組み合わせ
重複要素がある場合とない場合のリストのすべての順列を列挙し、すべての k-組み合わせと組み合わせ合計のバリエーションを生成します。
「順列と組み合わせ」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
順列と組合せ
順列は、順序が重要な並べ方です。[1,2,3] と [3,2,1] は異なるものとして扱います。n 個の要素の順列の数は n! です。組合せは、順序が重要でない選び方です。{1,2} を選ぶことと {2,1} を選ぶことは同じです。n 個の要素から k 個を選ぶ組合せの数は C(n,k) = n! / (k! × (n-k)!) です。どちらも、面接で出る数え上げ、列挙、選択に関する問題で不可欠なパターンです。
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)すべての順列の生成
現在のパスにどの要素が含まれているかを追跡するために、used のブール配列を使用します。各ステップで、まだ使っていない要素をすべて試します。探索が終わったら、その要素を再び未使用としてマークします。部分集合とは異なり、順列では要素をどの順序でも使うため、start インデックスはありません。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]]交換による順列生成
別の方法として、位置 start の要素を start から n-1 までの各要素と交換し、再帰処理を行った後で元に戻します。この方法では used 配列を使わず、配列をその場で変更します。重要な点は、各レベルで start より左側の要素がすべて確定しており、位置 start にどの要素を置くかを選んでいることです。こちらのほうがメモリ効率がやや高く、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：重複の処理
入力に重複がある場合（例: [1, 1, 2]）、used 配列を使う方法では重複した順列が生成されます。これを修正するには、配列をソートし、今回の再帰呼び出しで直前の同じ要素が使われていなければ、その重複要素をスキップします。条件は if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue です。これにより、重複する要素は常に左から右の順に選択されます。
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（辞書順）
Next Permutation（LeetCode 31）は、配列を辞書順で次に大きい順列へ、その場で変換します。アルゴリズムは次のとおりです。(1) nums[i] < nums[i+1] となる最も右のインデックス i を見つけます。(2) nums[j] > nums[i] となる最も右のインデックス j を見つけます。(3) nums[i] と nums[j] を交換します。(4) インデックス i より後ろのサフィックスを反転します。そのような i が存在しない場合は、配列全体を反転します（最小の順列に戻ります）。
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-組合せのバックトラッキング
n 個の要素から k 個を選ぶすべての組合せを生成します（LeetCode 77）。部分集合と同じように開始インデックスを使い、要素を再訪せず、順序を維持します。残りの要素数が k - len(path) 未満になったら枝刈りします。条件は if len(nums) - i + 1 < k - len(path): break です。これは、実際の配列を操作する点を除けば、先ほどの combine(n, k) と同じです。
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：無制限の再利用
Combination Sum（LeetCode 39）では、各数値を無制限に何度でも使用できます。通常の組合せとの違いは、start を i+1 に進めるのではなく、同じ要素を再利用できるように i のまま渡すことです。枝刈りの方法は、残りの target が 0 になったらパスを記録し、負になったら停止することです。ソートしておけば、残りの候補がすべて残りの 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：再利用なし、重複あり
Combination Sum II（LeetCode 40）では、各数値を最大 1 回だけ使いますが、入力には重複が含まれる場合があります。ここでは2つの手法を組み合わせます。start を i+1 に進めて再利用を防ぎ、ソートした後、同じレベルで重複をスキップします（if i > start and nums[i] == nums[i-1]: continue）。これは、Subsets II の重複処理と、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（LeetCode 17）は、電話のキーパッド上の各数字を文字に対応付け、与えられた数字列から考えられるすべての文字の組合せを生成します。これはバックトラッキングの問題で、各位置で数字に対応する文字を1つ選び、再帰します。長さ n の文字列で、各数字に対応する文字数の平均が k である場合、時間計算量は 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']順列と組合せの比較
主な構造上の違いは次のとおりです。順列 — 開始インデックスを使わず、再利用を防ぐために used 配列または交換を使います。各レベルで n 個の選択肢があり、葉は合計 n! 個です。組合せ — 順序を強制するために開始インデックスを使い、葉は C(n,k) 個です。Combination Sum — 再利用するために開始インデックスを進めず、target に基づいて枝刈りします。新しい問題をこの3つの形式のいずれかに対応付ければ、適切なテンプレートをすぐに選べます。
# 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}')計算量と面接のヒント
列挙の時間計算量は、順列が O(n × n!)、組合せが O(k × C(n,k))、Combination Sum が O(n^(T/min_val)) です。空間計算量は、再帰の深さに対して O(n)、結果の保存に対して O(output) です。重要なヒントは次のとおりです。(1) 順序が重要かどうか（順列か組合せか）を必ず確認します。(2) 質問される前に、重複の処理方法に触れます。(3) 枝刈り条件を必ず明示します。(4) n が大きい場合は、出力自体が指数サイズになるため、そのタスクに対してアルゴリズムが最適であることを説明します。
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)'クイックチェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念を理解できているか確認しましょう。
レッスンのまとめ
このレッスンでは、順列では used 配列と開始インデックスなしの方法を使い、n! 個の並べ方を生成すること、組合せでは再利用を防ぐために進める開始インデックスを使い、C(n,k) 個の選び方を生成すること、そしてどちらの問題でも、配列をソートし、同じ再帰レベルで繰り返される値をスキップすることで重複を処理することを学びました。次は、バックトラッキングを N-Queens 問題に適用し、制約伝播について学びます。
よくある質問
「順列と組み合わせ」レッスンは無料ですか？
はい。「順列と組み合わせ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「順列と組み合わせ」で何を学びますか？
重複要素がある場合とない場合のリストのすべての順列を列挙し、すべての k-組み合わせと組み合わせ合計のバリエーションを生成します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「順列と組み合わせ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。