39. Combination Sum

📝 Problem Details

• Title: 39. Combination Sum
• Link: https://leetcode.com/problems/combination-sum/
• Difficulty: Medium
• Tags/Categories: Backtracking

input array of distinct integers input integer target return a list of all unique combinations of elements where the chosen numbers sum to target the same number may be chosen from the input array an unlimited number of times two combinations are unique if the frequency of at least one of the chosen numbers are different

💭What Were My Initial Thoughts?

- enumeration problem: we need to find all possible combinations that sum up to target
- similar in nature to the problem Coin Change:
	- instead of minimizing the number of coins, we collect all valid ways to sum to target

- key choices 
	- include an element (can reuse it)
	- exclude an element (move to the next)

- constraint
	- we must stop searching when the sum exceeds target (invalid solution)
	- we can re-use elements as many times as needed

💡 Explanation of Solution

- base case: target == 0 --> a valid combination is found, store it
- for loop from index to size
	- if candidates[i] > target, prune it early 
	- include candidates[i] and explore recursively
	- dont move i+1 after inclusion, allows reuse of elements
	- backtrack (undo the choice) before moving to the next calculation 

⌛ Complexity Analysis

Time Complexity: O(2^n)
- reducing unecessary calls with pruning (practical reduction of complexity)

Space Complexity: O(2^n)
- storage of all possible computations in the worst case 

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> currentSubset;
        dfs(candidates, currentSubset, result, 0, target);
        return result;
    }
    
    void dfs(vector<int>& candidates, 
            vector<int>& currentSubset, 
            vector<vector<int>>& result,
            int index, 
            int target) {
 
        // base case: if target is 0, we found a valid combination
        if(target == 0) {
            result.push_back(currentSubset);
            return;
        }
 
        // explore choices
        for(int i = index; i < candidates.size(); i++) {
            if(candidates[i] > target) continue; // prune this tree if it exceeds target
 
            // choose
            currentSubset.push_back(candidates[i]);
 
            // explore (re-use the same element by not incrementing i)
            dfs(candidates, currentSubset, result, i, target-candidates[i]);
 
            // backtrack (undo the choice)
            currentSubset.pop_back();
        }
    }
};