Permutations & Combinations

    DSA · Intermediate

    Definition

    Permutations are ordered arrangements; combinations are unordered selections.

    Generating them is a core backtracking skill.

    Diagram

    [1 2 3]perms 6C(3,2) = 3

    Flowchart

    Pick an unused elementRecurseUndoCollect when length reached

    Example: itertools

    from itertools import permutations, combinations
print(len(list(permutations([1, 2, 3]))), list(combinations([1, 2, 3], 2)))

    Output: 6 [(1, 2), (1, 3), (2, 3)]

    Complexity

    Permutations O(n·n!) · Combinations O(C(n,k))

    Key points

    • nPr = n!/(n−r)!
    • nCr = n!/(r!(n−r)!)

    Interview questions

    Handle duplicates?

    Sort and skip equal elements at the same recursion level.

    More DSA topics

    ArraysLinked ListStackQueue