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 element is different.

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements in candidates are distinct.
• 1 <= target <= 40

Example:

Input:

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

Output:

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

---

Optimal Approach: Backtracking

Explanation:

Since we can pick elements multiple times and need all combinations that sum up to target, backtracking is the best approach.

1. Start with an empty combination and iterate through candidates.
2. If adding a number does not exceed target, recursively call the function with the reduced target.
3. If target becomes 0, store the valid combination.
4. Remove the last element (backtrack) and continue exploring other possibilities.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    void findCombinations(int index, vector<int>& candidates, int target, vector<int>& current, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(current);
            return;
        }
        for (int i = index; i < candidates.size(); i++) {
            if (candidates[i] <= target) {
                current.push_back(candidates[i]);
                findCombinations(i, candidates, target - candidates[i], current, result);
                current.pop_back(); // Backtrack
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        findCombinations(0, candidates, target, current, result);
        return result;
    }
};

---

Step-by-Step Explanation:

1. Base Case: If target == 0, store the current combination.
2. Loop Over Candidates: Iterate through numbers starting from index (to avoid duplicates).
3. Recursive Call: Subtract candidates[i] from target and continue.
4. Backtrack: Remove the last element and try other possibilities.

---

Dry Run with candidates = [2,3,6,7], target = 7

Step	Index	Current Combination	Remaining Target	Result
1	0	[]	7	[]
2	0	[2]	5	[]
3	0	[2,2]	3	[]
4	0	[2,2,2]	1	[]
5	0	[2,2,3]	0	[[2,2,3]]
6	1	[3]	4	[[2,2,3]]
7	1	[3,3]	1	[[2,2,3]]
8	2	[6]	1	[[2,2,3]]
9	3	[7]	0	[[2,2,3],[7]]

---

Alternative Approaches:

1. Brute Force (Generate All Subsequences)

• Time Complexity: O(2^n)
• Space Complexity: O(n) (recursion depth)
• Why Not? Too slow for large inputs.

2. Dynamic Programming (Subset Sum Variation)

• Time Complexity: O(n * target)
• Space Complexity: O(target)
• Why Not? Requires additional space and is less intuitive for this problem.

---

Best Solution & Comparison Table:

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Inefficient
Backtracking	O(2^n) (worst case)	O(n)	Best balance
DP	O(n * target)	O(target)	Overhead in space

Backtracking is the most intuitive and effective approach.

---

Complexity Analysis:

• Time Complexity: O(2^n) (Each number can either be included or not, leading to exponential growth.)
• Space Complexity: O(n), where n is the recursion depth.

---

Conclusion

• Best Approach: Backtracking is the most efficient due to its ability to prune branches early.
• Alternative Methods: Brute Force is inefficient, and DP has unnecessary overhead.
• Practice More: Try similar problems like:
  • Combination Sum II
  • Coin Change
  • Subset Sum

This ensures a strong grasp of recursion and dynamic programming.