MediumBacktracking

Combinations

Generate all k-combinations

Solution Approach

Recursively explore all possible solutions. Make choice, explore recursively, undo choice (backtrack). Use when searching permutations, combinations, or paths.

Implementation

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
    backtrack([], nums)
    return result

Complexity Analysis

Time Complexity

O(n!)

Space Complexity

O(n)

Key Learning Points

Recursive explorationUndo/backtrack stepUseful for all permutations/combinations