Backtracking: Permutations and Combinations

What is this?

Permutations are all the ways to arrange items in order, and combinations are all the ways to pick a group where order does not matter. Backtracking builds these one item at a time, undoing the last pick whenever it needs to try something else, like exploring every branching path in a maze. This lets you list every arrangement or selection without repeating or skipping any.

💡 Fun fact: The number of permutations grows astonishingly fast. Just 10 distinct items can be arranged in over 3.6 million different orders, which is why backtracking prunes dead ends early to stay efficient.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Overview

This chapter explores backtracking techniques for generating permutations and combinations, fundamental to solving combinatorial problems. These patterns appear frequently in coding interviews requiring exhaustive search with constraints.

Key Concepts

• Permutations: Arrangements of distinct items where order matters
• Combinations: Selections of items where order doesn't matter
• Backtracking Pruning: Early termination of invalid solution paths
• State Tracking: Managing used elements and current selections

Problems Covered

Permutations

• Key Insight: Generate all possible arrangements of distinct elements
• Technique: Backtracking with visited array or swap-based approach
• Complexity: O(N!) time due to exploring all arrangements

Combinations

• Key Insight: Select K elements from N without regard to order
• Technique: Backtracking with increasing start indices
• Optimization: Pruning when insufficient remaining elements

Combination Sum

• Key Insight: Find combinations that sum to target with unlimited reuse
• Technique: Backtracking with sorted candidates and pruning
• Edge Cases: Handling unlimited usage and target constraints

Beautiful Arrangement

• Key Insight: Count permutations satisfying divisibility constraints
• Technique: Backtracking with position-based validation
• Optimization: Early pruning of invalid number placements

Letter Case Permutation

• Key Insight: Generate all case variations of letters in string
• Technique: Backtracking or bit manipulation for case choices
• Complexity: O(2^L) where L is number of letters

Common Patterns

Permutation Generation

• Track used elements with boolean arrays
• Build arrangements position by position
• Backtrack by resetting used flags

Combination Generation

• Use start index to maintain non-decreasing order
• Avoid duplicates by incrementing start after selection
• Prune when remaining elements insufficient

Constraint Handling

• Validate constraints at each step
• Use sorting for efficient pruning
• Track multiple state variables (sums, counts, positions)

Real-World Applications

• Scheduling: Assigning tasks to time slots
• Resource Allocation: Distributing items with constraints
• String Processing: Generating variations and combinations
• Game Theory: Exploring move combinations

Interview Tips

• Recognize Patterns: Permutation vs combination vs subset problems
• Choose Data Structures: Arrays for small constraints, sets for lookups
• Optimize Early: Sort input for pruning opportunities
• Handle Edge Cases: Empty inputs, single elements, maximum constraints

Common Mistakes

• Incorrect Ordering: Forgetting to maintain sorted order in combinations
• Infinite Recursion: Not properly marking visited states
• Duplicate Results: Not handling reuse constraints correctly
• Missing Pruning: Checking constraints too late in recursion

Next Steps

Master these patterns before tackling:

• Subset sum and knapsack problems
• Advanced constraint satisfaction
• Graph coloring and other combinatorial optimization