Combination Sum using Backtracking in Python

Introduction to Combination Sum

The combination sum problem is a classic coding challenge. It requires finding all possible combinations of numbers that add up to a specific target. This article will guide you through the solution using Python, making it easy even for beginners.

Understanding the Problem

Combination sum involves selecting numbers from a list to reach a given target. The same number can be chosen multiple times. Let’s break down the solution step by step.

Implementing the Combination Sum Function

Step 1: Define the Recursive Function

The core of the solution is a recursive function. It explores all possible combinations of numbers.

def combination_sum(nums, target, start, path, res):
    if target == 0:
        res.append(path.copy())
        return
    if target < 0:
        return

    for i in range(start, len(nums)):
        path.append(nums[i])
        combination_sum(nums, target - nums[i], i, path, res)
        path.pop()

Step 2: Initialize and Call the Function

We need a helper function to initialize variables and call the recursive function.

def get_combination_sum(nums, target):
    res = []
    combination_sum(nums, target, 0, [], res)
    return res

Example Usage

Let’s see how to use these functions with an example.

nums = [2, 3, 6, 7]
target = 7
print(get_combination_sum(nums, target))

Expected Output

The output for the above example will be:

[[2, 2, 3], [7]]

This shows all combinations of numbers in nums that sum up to the target value.

Breaking Down the Code

Recursive Function Explanation

• Base Case: If the target is 0, we found a valid combination and add it to the result list.
• Termination Case: If the target is less than 0, we return without adding the combination.
• Recursive Case: We iterate through the list, add the current number to the path, call the function recursively with the updated target, and then backtrack by removing the number from the path.

Helper Function Explanation

• Initialization: We initialize an empty list res to store the results.
• Recursive Call: We call the recursive function with initial parameters.

Key Points to Remember

1. Recursion and Backtracking: The solution relies on these two concepts. Recursion explores possible combinations, while backtracking ensures we don’t miss any valid combinations.
2. Edge Cases: Consider edge cases such as empty lists or negative targets.

Conclusion

The combination sum problem is an excellent exercise for mastering recursion and backtracking. By following this guide, beginners can understand and implement the solution in Python. Practice with different sets of numbers and targets to strengthen your understanding.