Lesson

13.5Combination Sum

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

Note:
- The same number may be chosen from candidates an unlimited number of times.
- Two combinations are unique if the frequency of at least one of the chosen numbers is different.
- The solution set must not contain duplicate combinations.
- You may return the combinations in any order.

Example Inputs

Example 1:

Example 2:

Example 3:

Problem Solution

Approach

To find all unique combinations that sum up to the target, we can use a recursive backtracking approach. The key idea is to explore all possible combinations by choosing each candidate number and deciding whether to include it in the current combination or not. Since we can use the same number multiple times, after choosing a number, we can choose it again in the next recursive call.

Steps

Sort the Array (Optional):
- Sorting can help in optimizing the process by stopping early when the sum exceeds the target.
- However, since all numbers are distinct in this problem, it's not strictly necessary.
Initialize:
- Create an empty list ans to store all valid combinations.
- Create an empty list current to store the current combination being explored.
Recursive Backtracking Function (backtrack):
- Parameters: start (current index in candidates), target (remaining sum), current (current combination).
- Base Case:
  - If target is 0, it means the current combination sums up to the original target. Add a copy of current to ans.
  - If target becomes negative, stop exploring this path as it cannot lead to a valid combination.
- Recursive Case:
  - Iterate through the candidates starting from the start index to avoid duplicates.
  - For each candidate:
    - If the candidate is greater than the remaining target, skip it (optional optimization).
    - Include the candidate in current.
    - Recursively call backtrack with updated target (target - candidate) and the same start index (since the same number can be reused).
    - Remove the last candidate from current to backtrack and explore other possibilities.
Start Backtracking:
- Call the backtrack function starting from index 0 with the original target and an empty current combination.
Return the Result:
- After exploring all possibilities, return the ans list containing all valid combinations.

Time & Space Complexity

Time Complexity:
- O(2^n), where n is the number of candidates. In the worst case, the algorithm explores all possible combinations.
Space Complexity:
- O(n), where n is the number of candidates. This space is used by the recursion stack and the current combination list.

Code Snippet

Dry Run

Let's perform a dry run with candidates = [2, 3, 6, 7] and target = 7.

Initial Call: backtrack(0, 7)
- current = []
First Level (start = 0, target = 7):
- i = 0: Candidate = 2
  - Include 2: current = [2]
  - Recurse: backtrack(0, 5)
Second Level (start = 0, target = 5):
- i = 0: Candidate = 2
  - Include 2: current = [2, 2]
  - Recurse: backtrack(0, 3)
Third Level (start = 0, target = 3):
- i = 0: Candidate = 2
  - Include 2: current = [2, 2, 2]
  - Recurse: backtrack(0, 1)
Fourth Level (start = 0, target = 1):
- i = 0: Candidate = 2
  - 2 > 1, skip
- i = 1: Candidate = 3
  - 3 > 1, skip
- i = 2: Candidate = 6
  - 6 > 1, skip
- i = 3: Candidate = 7
  - 7 > 1, skip
- End of loop. Backtrack to current = [2, 2]
Back to Third Level (start = 0, target = 3):
- i = 1: Candidate = 3
  - Include 3: current = [2, 2, 3]
  - Recurse: backtrack(1, 0)
Fifth Level (start = 1, target = 0):
- target === 0, add [2, 2, 3] to ans
- Backtrack to current = [2, 2]
Back to Second Level (start = 0, target = 5):
- i = 1: Candidate = 3
  - Include 3: current = [2, 3]
  - Recurse: backtrack(1, 2)
Third Level (start = 1, target = 2):
- i = 1: Candidate = 3
  - 3 > 2, skip
- i = 2: Candidate = 6
  - 6 > 2, skip
- i = 3: Candidate = 7
  - 7 > 2, skip
- End of loop. Backtrack to current = [2]
Back to Second Level (start = 0, target = 5):
- i = 2: Candidate = 6
  - 6 > 5, skip
- i = 3: Candidate = 7
  - 7 > 5, skip
- End of loop. Backtrack to current = []
First Level (start = 0, target = 7):
- i = 1: Candidate = 3
  - Include 3: current = [3]
  - Recurse: backtrack(1, 4)
Second Level (start = 1, target = 4):
- i = 1: Candidate = 3
  - Include 3: current = [3, 3]
  - Recurse: backtrack(1, 1)
Third Level (start = 1, target = 1):
- i = 1: Candidate = 3
  - 3 > 1, skip
- i = 2: Candidate = 6
  - 6 > 1, skip
- i = 3: Candidate = 7
  - 7 > 1, skip
- End of loop. Backtrack to current = [3]
Back to Second Level (start = 1, target = 4):
- i = 2: Candidate = 6
  - 6 > 4, skip
- i = 3: Candidate = 7
  - 7 > 4, skip
- End of loop. Backtrack to current = []
First Level (start = 0, target = 7):
- i = 2: Candidate = 6
  - Include 6: current = [6]
  - Recurse: backtrack(2, 1)
Second Level (start = 2, target = 1):
- i = 2: Candidate = 6
  - 6 > 1, skip
- i = 3: Candidate = 7
  - 7 > 1, skip
- End of loop. Backtrack to current = []
First Level (start = 0, target = 7):
- i = 3: Candidate = 7
  - Include 7: current = [7]
  - Recurse: backtrack(3, 0)
Third Level (start = 3, target = 0):
- target === 0, add [7] to ans
- Backtrack to current = []
Final Result: [[2, 2, 3], [7]]

Complexity Analysis

Optimized Time and Space

The recursive backtracking approach explores all possible combinations by making a binary choice at each step: include the current candidate or exclude it.

Time Complexity: O(2^n), where n is the number of candidates. This is because each candidate can either be included or excluded, leading to 2^n possible combinations in the worst case.
Space Complexity: O(n), where n is the number of candidates. This space is used by the recursion stack and the current combination list.

Optimizations:

Early Termination: By skipping candidates that exceed the remaining target, we can reduce the number of recursive calls.
Avoiding Duplicates: Since all candidates are distinct in this problem, we don't need to handle duplicates explicitly. However, sorting can still help in optimizing the process.

Conclusion

The Combination Sum problem is a classic example of using recursive backtracking to explore all possible combinations that meet a specific criterion—in this case, summing up to a target value. By systematically choosing whether to include each candidate and exploring all viable paths, we can efficiently generate all unique combinations. Understanding this approach not only helps in solving similar combinatorial problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization.

Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for beginners. By breaking down the problem into smaller, manageable steps and applying systematic decision-making, we can tackle complex problems with confidence and clarity.

Previous Next