Medium
Related Topics: Array / Backtracking
LeetCode Source

解題想法

首先透過 sort 把 candidates 排序

接著透過 subset_sum 找尋不重複的組合

其組合可以加總為 target

最後回傳全部的組合

Complexity

Time Complexity: O(2^n * n)
Space Complexity: O(n)

Python

class Solution:
    def subset_sum(self, nums, target, partial, res):
        s = sum(partial)

        if s == target:
            res.append(partial)
            return

        if s >= target:
            return
        
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            n = nums[i]
            remain = nums[i+1:]
            self.subset_sum(remain, target, partial + [n], res)

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        candidates.sort()

        self.subset_sum(candidates, target, [], res)

        return res

C++

accumulate 可以加總所有 vector 的元素

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        std::vector<std::vector<int>> res;
        std::vector<int> partial;

        std::sort(candidates.begin(), candidates.end());
        subset_sum(candidates, target, partial, res, 0);

        return res;
    }

    void subset_sum(vector<int>& nums, int target, vector<int>& partial, vector<vector<int>>& res, int start) {
        int s = accumulate(partial.begin(), partial.end(), 0);

        if (s == target) {
            res.push_back(partial);
            return;
        }
            
        if (s > target)
            return;
        
        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            partial.push_back(nums[i]);
            subset_sum(nums, target, partial, res, i + 1);
            partial.pop_back();
        }
    }
};