LeetCode: Backtracking

Intro

Backtracking is a technique where we incrementally build candidates for solutions and abandon or 'backtrack' a candidate when it cannot lead to a valid solution.

The key idea is recursive exploration to build solutions while pruning invalid branches.

Backtracking commonly leads to high time complexity is often the most practical way to solve certain types of problem that require an exhaustive search exploring all possibilities.

Example: Sum of a Subset

Given a list of integers and a target sum, find all subsets that add up to the target.

Solution 1: Backtracking

    def subsetSum(self, nums, target):
        
        # store valid results
        result = []

        def backtrack(current, index, total):
            
            # Prune the path if the total exceeds the target
            if total > target:
                return

            # If total matches the target, add to result
            if total == target:
                result.append(list(current))
                return

            # Explore further candidates
            for i in range(index, len(nums)):
                # Choose
                current.append(nums[i])

                # Recurse
                backtrack(current, i + 1, total + nums[i])

                # Undo the choice (backtrack)
                current.pop()

        backtrack([], 0, 0)

        # overall: time complexity
        # overall: space complexity
        return result

Backtracking for: [2, 6, 7, 10, 15]
                                                  [] 
                     Include 2                                           Exclude 2
                    /                                                          \
                   [2]                                                         []
          Include 6   Exclude 6                                       Include 6   Exclude 6     
           /              \                                            /                 \
       [2,6]              [2]                                      [6]                  []
        Prune      Include 7  Exclude 7                    Include 7  Exclude 7        Include 7  Exclude 7
                       /           \                         /              \           /              \
                    [2,7]          [2]                     [6,7]           [6]        [7]              []
                    Prune    Include 10  Exclude 10        Prune          ....     Solution           ...
                                /           \
                               [10]         []
                               Prune        ...