LeetCode Solution 39 - Combination 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. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one number is different.

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• All elements of candidates are distinct.
• 1 <= target <= 500

Optimal Approach - Backtracking

The most efficient way to solve this problem is using Backtracking with recursion.

Explanation:

1. Sort the candidates array to improve efficiency (optional but helpful).
2. Use a recursive function to explore different combinations.
3. Maintain an index to avoid duplicate combinations.
4. Backtrack when the sum exceeds the target.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    void backtrack(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int>& temp, int start) {
        if (target == 0) {
            result.push_back(temp);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) continue; // Skip if the number exceeds target
            temp.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], result, temp, i); // Reuse the same element
            temp.pop_back(); // Backtrack
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> temp;
        backtrack(candidates, target, result, temp, 0);
        return result;
    }
};

Step-by-Step Explanation

1. Base Case: If target == 0, add the current combination to the result.
2. Recursive Call: Iterate through candidates, subtract from target, and recurse.
3. Backtrack: Remove the last added element before moving to the next.

Dry Run / Execution Steps

Example:

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

Execution Tree:

                        [] (target = 7)
                      /  |  \   \
                   [2]  [3] [6] [7]
                  /  |    |      |
              [2,2] [2,3] [3,3]  [7] (Valid)
              /    |   |
        [2,2,2] [2,2,3] (Valid)

Output:

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

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force	Exponential $O(2^n)$	O(n)	Inefficient for large inputs
Dynamic Programming	O(n*target)	O(target)	Not suitable due to repeated subsets
Backtracking (Best)	O(2^n)	O(n)	Best balance of efficiency and flexibility

Best Solution & Why It’s Best

The Backtracking approach is optimal because:

1. It efficiently prunes branches where the sum exceeds the target.
2. It finds all valid combinations without extra space like DP.
3. It ensures unique combinations by maintaining the starting index.

Complexity Analysis

• Time Complexity: O(2^n), as we explore subsets recursively.
• Space Complexity: O(n), due to recursive stack depth.

Conclusion

• The best approach is Backtracking.
• Other methods like brute force or DP are less efficient.
• Recommended practice problems:
  • Combination Sum II (LeetCode 40)
  • Subset Sum (LeetCode 698)
  • Partition Equal Subset Sum (LeetCode 416)