Leetcode-40Combination Sum II

40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

题解：

输入一个有重复元素的数组，列出该数组的所有子集中，满足子集中各元素的和为target的子集；
我们在 Leetcode90：https://www.jianshu.com/p/07ce8871be7f 中，已经能够获得有重复元素的数组中的所有子集，所以只需要在 item 存入 result 前再判断一下是否 item 的元素和为 target 即可；
为了提高效率，我们可以把 item 元素的和大于 target 的情况进行剪枝，不继续递归；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        int i = 0;
        int sum = 0;
        sort(candidates.begin(), candidates.end());
        vector<int> item;
        vector<vector<int>> result;
        set<vector<int>> judge;
        add_item(i, sum, target, candidates, judge, item, result);
        return result;
    }
private:
    void add_item(int i, int sum, int target, vector<int> &candidates, set<vector<int>> &judge, vector<int> &item, vector<vector<int>> &result) {
        if (i >= candidates.size() || sum > target) {
            return;
        }
        item.push_back(candidates[i]);
        sum += candidates[i];
        if (judge.find(item) == judge.end() && sum == target) {
            result.push_back(item);
            judge.insert(item);
        }
        add_item(i + 1, sum, target, candidates, judge, item, result);
        item.pop_back();
        sum -= candidates[i];
        add_item(i + 1, sum, target, candidates, judge, item, result);
    }
};

int main() {
    vector<vector<int>> result;
    vector<int> candidates;
    candidates.push_back(10);
    candidates.push_back(1);
    candidates.push_back(2);
    candidates.push_back(7);
    candidates.push_back(6);
    candidates.push_back(1);
    candidates.push_back(5);
    Solution s;
    result = s.combinationSum2(candidates, 8);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%d]", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

结果：

[1][1][6]
[1][2][5]
[1][7]
[2][6]

My Solution（Python）：

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        item = []
        candidates.sort(reverse=True)
        self.each_sum(0, candidates, target, 0, item, result)
        return result

    def each_sum(self, i, candidates, target, sum_all, item, result):
        if i >= len(candidates) or sum_all >= target:
            return
        item.append(candidates[i])
        sum_all += candidates[i]
        if sum_all == target:
            if result.count(item) == 0:
                item_data = item.copy()
                result.append(item_data)
        self.each_sum(i + 1, candidates, target, sum_all, item, result)
        item.pop()
        sum_all -= candidates[i]
        self.each_sum(i + 1, candidates, target, sum_all, item, result)

Reference:

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        dp = [set() for i in range(target+1)]
        dp[0].add(())
        for num in candidates:
            for t in range(target, num-1, -1):
                for prev in dp[t-num]:
                    dp[t].add(prev + (num,))
        return list(dp[-1])