39. Combination Sum - cocoder39/coco39_LC GitHub Wiki

39. Combination Sum

repeated elements are accepted, thus duplication can be avoided after sorting.

Notes 2024:

solution 1: sort based deduping

N be the number of candidates, T be the target value, and M be the minimal value among the candidates

upper bound Time: O(N ^ (T/M + 1)) N branches at each level and (T/M + 1) levels Space: O(T/M)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        self.helper(candidates, target, 0, [], res)
        return res
    
    
    def helper(self, candidates, target, start, path, res):
        if target == 0:
            res.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                break
            path.append(candidates[i])
            self.helper(candidates, target-candidates[i], i, path, res)
            path.pop()

solution 2: hash based dedup solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = set()
        self.helper(0, 0, [], res, target, candidates)
        return list(res)

    def helper(self, start, path_sum, path, res, target, candidates):
            if path_sum == target:
                res.add(tuple(sorted(path)))
                return
            
            if path_sum > target:
                return
            
            first_pick = set() # pruning
            for i in range(start, len(candidates)):
                if candidates[i] in first_pick:
                    continue
                first_pick.add(candidates[i])
                path.append(candidates[i])
                self.helper(i, path_sum + candidates[i], path, res, target, candidates)
                path.pop()

time complexity: according to 40. Combination Sum II, where time complexity is O(k * 2 ^ n). Here our n is not candidates.size() anymore since repeated elements are considered. Given [2, 3, 4, 5, 6], the corresponding input in 40. Combination Sum II would be [2, 2, 2, 2, 2, 3, 3 ,3, 3 , 4, 4, 4, 5, 5, 6, 6]. In other words, each unique element a would be expanded ceil(target / a) times, generating new length n'. Hence the time complexity is O(k * 2 ^ n')

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //if there exists negative number, then we have to check all combinations
        //positive helps us prune solution set
        //sort helps avoid duplicate
        vector<vector<int>> res;
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        helper(res, cur, candidates, 0, target);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, vector<int>& cands, int start, int target) {
        if (target == 0) {
            res.push_back(cur);
            return;
        }
        else if (cands[start] > target) {
            return;
        }
        
        for (int i = start; i < cands.size(); i++) {
            cur.push_back(cands[i]);
            helper(res, cur, cands, i, target - cands[i]);
            cur.pop_back();
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️