40. Combination Sum II - cocoder39/coco39_LC GitHub Wiki

40. Combination Sum II

Notes 2020:

Notes 2020: Main idea is combination-sum + SubsetII

class Solution:
    def combinationSum2(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
        elif start == len(candidates) or candidates[start] > target:
            return
        
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            self.helper(candidates, target-candidates[i], i+1, path, res)
            path.pop()

Time complexity: k = target/min_element then time complexity is same as finding all combinations (eg, LC77). O(K * C(N, K)). Difference between Combination Sum (O (N ^K)) is that Combination Sum II doesn't allow reuse of each element.

solution 2: hash based de-dup

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = set()
        self.helper(candidates, target, res, 0, [])
        return list(res)
    
    def helper(self, candidates, target, res, start, combination):
        if target == 0:
            res.add(tuple(sorted(combination)))

        first_pick = set()
        for i in range(start, len(candidates)):
            if candidates[i] in first_pick or target < candidates[i]:
                continue
            

            first_pick.add(candidates[i])

            combination.append(candidates[i])
            self.helper(candidates, target-candidates[i], res, i+1, combination)
            combination.pop()

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

key is to avoid duplication through if (i - 1 >= start && cands[i] == cands[i - 1]).

time complexity: as discussed in 77. Combinations where the complexity of choosing k elements from n elements is O(C(k, n)). Here we may choose 1 - n elements. Hence the time complexity is O(C(1, n) + C(2, n) .. C(n, n)) = O(2 ^ n).Thus final time complexity is O(k * 2 ^ n) where k is average length of chosen subset and n is candidates.size().

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        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 (target < cands[start]) {
            return;
        }
        for (int i = start; i < cands.size(); i++) {
            if (i - 1 >= start && cands[i] == cands[i - 1]) {
                continue;
            }
            cur.push_back(cands[i]);
            helper(res, cur, cands, i + 1, target - cands[i]);
            cur.pop_back();
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️