40. Combination Sum II --- M

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

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

Note: The solution set must not contain duplicate combinations.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

 

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

A:

-------------递归--------每次分情况计算后，再合并。类似于bfs --------

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

sort(candidates.begin(), candidates.end());

return helper(candidates, 0, target);

}

private:

vector<vector<int>> helper(vector<int>& candidates, int start, int target) {

int n = candidates.size();

if (target < 0) {

return {};

} else if (target == 0) {

return {{}};

}

if (start >= n)

return {};

// get count of candidates[start]

int count = 1;

for (int i = start + 1; i < n; i++) {

if (candidates[i] == candidates[start]) {

count++;

} else {

break;

}

}

auto res = helper(candidates, start + count, target); // not used

for (int c = 1; c <= count; c++) {

auto used = helper(candidates, start + count,

target - candidates[start] * c);

for (auto v : used) {

for (int i = 0; i < c; i++) {

v.push_back(candidates[start]);

}

res.push_back(v);

}

}

return res;

}

};

Mistakes：

1: 递归的结束条件，需要好好考虑。 好几个错误，在这里

2: for loop 里， start + count .因为不用这个start的值了 

    

还有一种递归的方式，跟39. combination sum 一样，是用dfs 先深入到target == 0 . 

-----------C++  -------iterative ------------

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& C, int target) {
        std::sort(C.begin(), C.end());
        vector<vector<int>> res, tmpRes={{}};
        vector<int> sumList = {0};
        
        for(int i =0;i<C.size(); i++)
        {
            int val = C[i], nVal = 1;
            while( i+1 < C.size() && C[i+1] == val ) // count of current val
            {
                i++;
                nVal++;
            }
            int curCount = tmpRes.size();
            for(int j = 0; j< curCount; ++j)
            {
                auto B = tmpRes[j];
                auto curSum = sumList[j];
                for(int k = 0; k<nVal; k++)
                {
                    B.push_back(val);
                    curSum += val;
                    if (curSum < target){ // add to next round
                        auto C = B; //must create a copy, as B can change next round
                        tmpRes.push_back(C);
                        sumList.push_back(curSum);
                    }else if(curSum == target){
                        res.push_back(B);
                    }
                }
            }            
        }        
        return res;        
    }
};

Learned: