Combination Sum Leetcode Problem 39 [Python Solution]

In the realm of LeetCode challenges, the Combination Sum problem, tagged under category "Backtracking," poses an intriguing puzzle.

This problem is a part of the Blind 75 list, a curated set of LeetCode problems designed to enhance your problem-solving skills.

So, let's dive into solving the Combination Sum problem!

Problem Overview

Question: Given an array of distinct integers candidates and a target integer target, how can we return a list of all unique combinations of candidates where the chosen numbers sum to the target?

It's important to note that you may return the combinations in any order.

Additionally, you are allowed to select the same number from candidates an unlimited number of times.

However, two combinations are considered unique if the frequency of at least one of the chosen numbers is different.

Example 1:

Input:

candidates = [2, 3, 6, 7]
target = 7


Output:

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


Explanation:
– In this example, we can choose 2 and 3, and 2 + 2 + 3 equals 7. It's essential to note that 2 can be used multiple times.
– 7 is also a candidate, and 7 equals 7. These are the only two unique combinations.

Example 2:

Input:

candidates = [2, 3, 5]
target = 8


Output:

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]


Example 3:

Input:

candidates = [2]
target = 1


Output:

[]


Constraints:
– 1 <= candidates.length <= 30
– 2 <= candidates[i] <= 40
– All elements of candidates are distinct.
– 1 <= target <= 40

Understanding the Constraints

Before we jump into the problem-solving, let's understand the constraints:

1. The length of the candidates array can be at most 30.
2. The candidates' values range from 2 to 40, and they are distinct.
3. The target value can range from 1 to 40.

Combination Sum LeetCode Problem Solution

To solve this problem efficiently, we can employ a backtracking approach.

This approach explores all possible combinations to find those that sum up to the target.

We'll use a recursive function to build these combinations.

Let's break down our solution into a step-by-step process:

1. Bruteforce Approach

We can think of this problem as constructing a decision tree where each node represents a choice: either to include a number from the candidates or skip it.

We traverse this decision tree to find valid combinations.

The key insight is that we'll start with the target value and keep subtracting the candidate values as long as the target remains non-negative.

When it reaches zero, we've found a valid combination.

If it goes negative, we backtrack and explore other possibilities.

2. An Efficient Approach with Pseudo Code

Now that we've established the brute-force approach, let's optimize it by using a backtracking technique.

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    res = []

    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if i >= len(candidates) or total > target:
            return

        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])
        cur.pop()
        dfs(i + 1, cur, total)

    dfs(0, [], 0)
    return res

Let's break down the efficient approach:

• We create a function dfs (depth-first search) that takes three parameters:
  • i: The index of the current candidate.
  • cur: A list that stores the current combination.
  • total: The current sum of the elements in the combination.
• The function dfs is responsible for exploring all possible combinations.
• We check for the base cases:
  • If total equals the target, we've found a valid combination, so we add it to the result.
  • If i goes out of bounds (greater than or equal to the length of candidates) or total exceeds the target, we return without continuing.
• If none of the base cases is met, we include the current candidate in the combination, update the sum, and recursively call dfs with the same index.
• After the recursive call, we pop the candidate from cur to backtrack and explore other possibilities.
• We call dfs initially with the starting index, an empty cur, and a total of 0.
• Finally, we return the res array, which contains all the unique combinations that sum up to the target.

Time and Space Complexity

Now, let's analyze the time and space complexity of our solution:

• Time Complexity: The time complexity is determined by the number of recursive calls.

In the worst case, each recursive call splits into two more calls.

Therefore, the time complexity is O(2^t), where t is the target value.

• Space Complexity: The space complexity is dominated by the recursion stack and the res array to store the results.

In the worst case, the recursion depth can be t, and the space complexity is O(t) for the stack.

The res array's space complexity is O(k * n), where k is the number of valid combinations, and n is the length of the candidates array.

Reasoning Behind Our Approach

Our backtracking approach allows us to explore all possible combinations systematically while avoiding duplicates.

By keeping track of the current combination and sum, we can efficiently identify valid combinations.

The key to this approach is the recursive function dfs, which intelligently traverses the decision tree, leading to a clear and elegant solution.

Related Interview Questions By Company:

• Range Sum Query 2D Immutable LeetCode
• Jump Game II LeetCode
• Rotate List LeetCode

Related Interview Questions By Difficulty:

• Matchsticks To Square LeetCode
• Combination Sum LeetCode
• Subsets LeetCode

Related Interview Questions By Category:

• Is Subsequence LeetCode
• Number Of Subsequences That Satisfy The Given Sum Condition LeetCode
• Reverse Bits LeetCode

Conclusion

The Combination Sum problem on LeetCode, designated as Problem 39, challenges your understanding of backtracking and recursive algorithms.

By efficiently exploring the decision tree of combinations, we can find all unique combinations that sum up to the target.

The backtracking approach outlined in this article is a powerful technique for solving various combinatorial problems.

We hope this guide has been helpful in understanding the problem and implementing a Python solution.

Remember that practice makes perfect, so keep honing your skills by solving more LeetCode problems.

If you have any questions, suggestions, or insights, please feel free to comment and share your thoughts.

Happy coding, and may you enjoy the journey of problem-solving and algorithms!

Question Link