Intermediate

Permutations & Combinations

Permutations care about order (ABC ≠ BAC), combinations do not (ABC = BAC). Both use the backtracking template but differ in how they manage the start index and visited tracking. These patterns appear in feature selection for ML models and in generating candidate configurations for hyperparameter search.

Problem 1: Permutations (LC 46)

Problem: Given an array of distinct integers, return all possible permutations.

Example: nums = [1, 2, 3] → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Brute Force: Generate All and Filter

from itertools import permutations as itertools_perms

def permute_brute(nums: list[int]) -> list[list[int]]:
    """Generate all permutations using itertools.

    Time: O(n! * n), Space: O(n! * n)
    Works but does not demonstrate understanding.
    Interviewers want to see the backtracking approach.
    """
    return [list(p) for p in itertools_perms(nums)]

Optimal: Backtracking with Visited Set

def permute(nums: list[int]) -> list[list[int]]:
    """Generate all permutations via backtracking.

    Decision tree: at each level, choose any unused element.
    Level 0: choose from all n elements
    Level 1: choose from remaining n-1 elements
    ...continues until path has n elements.

    Time: O(n! * n) - n! permutations, O(n) to copy each
    Space: O(n) for recursion depth + path
    """
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if i in used:
                continue
            used.add(i)
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used.remove(i)

    backtrack([], set())
    return result

# Example usage:
# permute([1, 2, 3])
# -> [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Problem 2: Permutations II (LC 47)

Problem: Given an array that might contain duplicates, return all unique permutations.

Example: nums = [1, 1, 2] → [[1,1,2], [1,2,1], [2,1,1]]

Brute Force: Generate All, Use Set to Deduplicate

def permute_unique_brute(nums: list[int]) -> list[list[int]]:
    """Generate all permutations and deduplicate with a set.

    Time: O(n! * n), Space: O(n! * n)
    Wasteful: generates duplicates then discards them.
    """
    result = set()

    def backtrack(path, used):
        if len(path) == len(nums):
            result.add(tuple(path))
            return
        for i in range(len(nums)):
            if i in used:
                continue
            used.add(i)
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used.remove(i)

    backtrack([], set())
    return [list(p) for p in result]

Optimal: Sort + Skip Duplicates at Same Level

def permute_unique(nums: list[int]) -> list[list[int]]:
    """Unique permutations via backtracking with pruning.

    Key insight: sort the array, then skip duplicates at the
    same recursion level. A duplicate at index i is skipped if
    nums[i] == nums[i-1] AND nums[i-1] was not used in this branch.

    Time: O(n! * n) worst case, faster with duplicates due to pruning
    Space: O(n) recursion depth
    """
    nums.sort()
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if i in used:
                continue
            # Skip duplicate: same value as previous, and previous
            # was NOT used (meaning it was skipped at this level)
            if i > 0 and nums[i] == nums[i - 1] and (i - 1) not in used:
                continue

            used.add(i)
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used.remove(i)

    backtrack([], set())
    return result

# permute_unique([1, 1, 2]) -> [[1,1,2], [1,2,1], [2,1,1]]

Problem 3: Combinations (LC 77)

Problem: Given two integers n and k, return all possible combinations of k numbers chosen from 1 to n.

Example: n = 4, k = 2 → [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Brute Force: Nested Loops

def combine_brute(n: int, k: int) -> list[list[int]]:
    """Generate combinations with nested loops.

    Only works for small, fixed k. Not generalizable.
    For k=2 this uses 2 nested loops, k=3 needs 3 loops, etc.

    Time: O(n^k), Space: O(C(n,k) * k)
    """
    if k == 2:
        return [[i, j] for i in range(1, n + 1)
                       for j in range(i + 1, n + 1)]
    # Cannot generalize without recursion
    raise NotImplementedError("Need recursion for arbitrary k")

Optimal: Backtracking with Start Index

def combine(n: int, k: int) -> list[list[int]]:
    """Generate all C(n,k) combinations via backtracking.

    Use start index to ensure we only pick elements after
    the last chosen one, avoiding duplicate combinations.

    Pruning: if remaining elements (n - i + 1) cannot fill
    the remaining slots (k - len(path)), skip.

    Time: O(C(n,k) * k), Space: O(k) recursion depth
    """
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return

        # Pruning: need (k - len(path)) more elements,
        # so i can go at most to n - (k - len(path)) + 1
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

# combine(4, 2) -> [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Problem 4: Combination Sum (LC 39)

Problem: Given an array of distinct integers candidates and a target, find all unique combinations where the chosen numbers sum to target. Each number may be used unlimited times.

Example: candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]]

Brute Force: Generate All Subsets, Filter by Sum

def combination_sum_brute(candidates: list[int], target: int) -> list[list[int]]:
    """Generate all possible combinations (with repeats) and filter.

    Extremely wasteful: explores far beyond the target sum.
    Time: Exponential, Space: Exponential
    """
    result = []

    def generate(idx, path, current_sum):
        if current_sum == target:
            result.append(path[:])
            return
        if current_sum > target or idx >= len(candidates):
            return
        # Include current element (can reuse)
        path.append(candidates[idx])
        generate(idx, path, current_sum + candidates[idx])
        path.pop()
        # Skip current element
        generate(idx + 1, path, current_sum)

    generate(0, [], 0)
    return result

Optimal: Backtracking with Sum Pruning

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    """Find combinations that sum to target (elements reusable).

    Key insight: sort candidates first, then prune when
    remaining sum is less than the smallest available candidate.
    Pass the same index i (not i+1) to allow reuse.

    Time: O(n^(T/M)) where T=target, M=min candidate
    Space: O(T/M) recursion depth
    """
    candidates.sort()
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # Pruning: if current candidate exceeds remaining, all
            # future candidates will too (array is sorted)
            if candidates[i] > remaining:
                break

            path.append(candidates[i])
            # Pass i (not i+1) because we can reuse the same element
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

# combination_sum([2,3,6,7], 7) -> [[2,2,3], [7]]

Problem 5: Letter Case Permutation (LC 784)

Problem: Given a string s, return all possible strings formed by changing each letter to uppercase or lowercase.

Example: s = "a1b2" → ["a1b2", "a1B2", "A1b2", "A1B2"]

Brute Force: Bit Masking on All Positions

def letter_case_brute(s: str) -> list[str]:
    """Use bit masking to generate all case variations.

    Treats every character as a toggle position, even digits.
    Then filters out invalid results. Wasteful for digit-heavy strings.

    Time: O(2^n * n), Space: O(2^n * n)
    """
    letters = [i for i, c in enumerate(s) if c.isalpha()]
    n = len(letters)
    result = []

    for mask in range(1 << n):
        chars = list(s)
        for j in range(n):
            idx = letters[j]
            if mask & (1 << j):
                chars[idx] = chars[idx].upper()
            else:
                chars[idx] = chars[idx].lower()
        result.append("".join(chars))

    return result

Optimal: Backtracking Only on Letters

def letter_case_permutation(s: str) -> list[str]:
    """Generate all letter case permutations via backtracking.

    At each position:
    - If digit: only one choice, continue
    - If letter: two choices (lower, upper), branch

    Time: O(2^L * n) where L = number of letters
    Space: O(n) recursion depth
    """
    result = []

    def backtrack(idx, path):
        if idx == len(s):
            result.append("".join(path))
            return

        if s[idx].isalpha():
            # Branch 1: lowercase
            path.append(s[idx].lower())
            backtrack(idx + 1, path)
            path.pop()

            # Branch 2: uppercase
            path.append(s[idx].upper())
            backtrack(idx + 1, path)
            path.pop()
        else:
            # Digit: only one choice
            path.append(s[idx])
            backtrack(idx + 1, path)
            path.pop()

    backtrack(0, [])
    return result

# letter_case_permutation("a1b2") -> ["a1b2", "a1B2", "A1b2", "A1B2"]

Complexity Summary

Problem	Brute Force	Optimal	Key Optimization
Permutations	O(n! × n)	O(n! × n)	Visited set avoids re-scanning
Permutations II	O(n! × n)	O(n! × n) with pruning	Sort + skip same-level duplicates
Combinations	O(nk)	O(C(n,k) × k)	Start index + upper bound pruning
Combination Sum	Exponential	O(nT/M)	Sort + break when candidate > remaining
Letter Case Perm	O(2n × n)	O(2L × n)	Only branch on letters, not digits