Combinations and Subsets

These are the most common backtracking problems. Master these patterns and you'll handle most interview questions.

Problem 1: Subsets (Power Set)

Problem: Generate all possible subsets of a set.

def subsets(nums):
    """
    Input: [1,2,3]
    Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    """
    result = []
    current = []

    def backtrack(start):
        # Every state is a valid subset
        result.append(current[:])

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1)  # Move forward, don't reuse
            current.pop()

    backtrack(0)
    return result

print(subsets([1, 2, 3]))

Time: O(n · 2ⁿ) - 2ⁿ subsets, O(n) to copy each Space: O(n) recursion depth

Key Pattern: Include every intermediate state as a solution.

Problem 2: Subsets II (With Duplicates)

Problem: Generate subsets when input has duplicates.

def subsets_with_dup(nums):
    """
    Input: [1,2,2]
    Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
    """
    result = []
    current = []
    nums.sort()  # Sort to group duplicates

    def backtrack(start):
        result.append(current[:])

        for i in range(start, len(nums)):
            # Skip duplicates: only take first of each duplicate group
            if i > start and nums[i] == nums[i-1]:
                continue

            current.append(nums[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return result

print(subsets_with_dup([1, 2, 2]))

Key Insight: Sort first, then skip duplicates at same level.

Problem 3: Combinations

Problem: Find all combinations of k numbers from 1 to n.

def combine(n, k):
    """
    Input: n=4, k=2
    Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
    """
    result = []
    current = []

    def backtrack(start):
        # Base case: collected k numbers
        if len(current) == k:
            result.append(current[:])
            return

        # Optimization: stop if not enough numbers left
        needed = k - len(current)
        available = n - start + 1
        if available < needed:
            return

        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1)
            current.pop()

    backtrack(1)
    return result

print(combine(4, 2))

Optimization: Early termination when not enough elements remain.

Problem 4: Combination Sum

Problem: Find all combinations that sum to target. Can reuse numbers.

def combination_sum(candidates, target):
    """
    Input: candidates=[2,3,6,7], target=7
    Output: [[2,2,3],[7]]
    """
    result = []
    current = []

    def backtrack(start, remaining):
        # Base case: exact target
        if remaining == 0:
            result.append(current[:])
            return

        # Prune: exceeded target
        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            current.append(candidates[i])
            # i (not i+1) because we can reuse
            backtrack(i, remaining - candidates[i])
            current.pop()

    backtrack(0, target)
    return result

print(combination_sum([2, 3, 6, 7], 7))

Key: Pass i instead of i+1 to allow reuse.

Problem 5: Combination Sum II

Problem: Find combinations that sum to target. Can't reuse, input has duplicates.

def combination_sum2(candidates, target):
    """
    Input: candidates=[10,1,2,7,6,1,5], target=8
    Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
    """
    result = []
    current = []
    candidates.sort()  # Sort for duplicate handling

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

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            # Skip duplicates at same level
            if i > start and candidates[i] == candidates[i-1]:
                continue

            current.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])  # i+1: no reuse
            current.pop()

    backtrack(0, target)
    return result

print(combination_sum2([10,1,2,7,6,1,5], 8))

Key: Combine duplicate skipping with sum pruning.

Problem 6: Letter Combinations of Phone Number

Problem: Generate all letter combinations from phone number digits.

def letter_combinations(digits):
    """
    Input: "23"
    Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
    """
    if not digits:
        return []

    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi',
        '5': 'jkl', '6': 'mno', '7': 'pqrs',
        '8': 'tuv', '9': 'wxyz'
    }

    result = []
    current = []

    def backtrack(index):
        # Base case: used all digits
        if index == len(digits):
            result.append(''.join(current))
            return

        # Get letters for current digit
        letters = phone[digits[index]]

        for letter in letters:
            current.append(letter)
            backtrack(index + 1)
            current.pop()

    backtrack(0)
    return result

print(letter_combinations("23"))

Key: Map choices to current position, recurse to next position.

Problem 7: Generate Parentheses

Problem: Generate all valid combinations of n pairs of parentheses.

def generate_parenthesis(n):
    """
    Input: n=3
    Output: ["((()))","(()())","(())()","()(())","()()()"]
    """
    result = []
    current = []

    def backtrack(open_count, close_count):
        # Base case: used all parentheses
        if len(current) == 2 * n:
            result.append(''.join(current))
            return

        # Can add '(' if we haven't used n yet
        if open_count < n:
            current.append('(')
            backtrack(open_count + 1, close_count)
            current.pop()

        # Can add ')' if it matches an '('
        if close_count < open_count:
            current.append(')')
            backtrack(open_count, close_count + 1)
            current.pop()

    backtrack(0, 0)
    return result

print(generate_parenthesis(3))

Key: Track constraints (open/close counts) to ensure validity.

Problem 8: Permutations

Problem: Generate all permutations of an array.

def permutations(nums):
    """
    Input: [1,2,3]
    Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    """
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            current.append(nums[i])
            used[i] = True
            backtrack()
            used[i] = False
            current.pop()

    backtrack()
    return result

print(permutations([1, 2, 3]))

Alternative without used array:

def permutations_v2(nums):
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return

        for i in range(len(remaining)):
            backtrack(
                current + [remaining[i]],
                remaining[:i] + remaining[i+1:]
            )

    backtrack([], nums)
    return result

Common Patterns Summary

Tips

1. Sort for duplicates: Always sort input when handling duplicates
2. Skip at same level: if i > start and nums[i] == nums[i-1]
3. Reuse vs not: backtrack(i) vs backtrack(i+1)
4. Track used: Array or set for permutation problems
5. Early pruning: Stop when target exceeded or not enough elements

Practice Template

def solve(nums):
    result = []
    current = []
    # nums.sort()  # If needed for duplicates

    def backtrack(start):
        # Base case
        if is_complete(current):
            result.append(current[:])
            return

        for i in range(start, len(nums)):
            # Skip duplicates if needed
            # if i > start and nums[i] == nums[i-1]:
            #     continue

            current.append(nums[i])
            backtrack(i + 1)  # or i for reuse, or no param for permutations
            current.pop()

    backtrack(0)
    return result