Combination Sum II

标签： C++ 算法 LeetCode DFS

每日算法——leetcode系列

---

问题 Combination Sum II

Difficulty: Medium

Given a set 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.

• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 >≤ … ≤ ak).>
• 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]

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
    }
};

翻译

和的组合

难度系数：中等

给定一个一些数组成的候选集合C，和一个目标数T。现从C中选出一些数，求所有不同的取数方案使其累加和恰好等于T。
C中的每个数都只能用一次。

注意

• 所有的数（包括目标数）都为正整数
• 组合中的元素(a1, a2, … , ak) 不能为降序排列。(ie, a1 ≤ a2 >≤ … ≤ ak)
• 不能有重复的组合方案
  例如：候选集合10,1,2,7,6,1,5 和目标值8,
  答案为：
  [1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

思路

和Combination Sum很像，只是这里不能重复取一个元素，但根据例子看是元素是有重复元素的。
这样就得去重复。

代码

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        len = static_cast<int>(candidates.size());
        temAndidates = candidates;
        vector<int> combination;
        dfs(combination, target, 0);
        return result;
    }
    
private:

    void dfs(vector<int>& combination, int remainder,  int tempLen){
        if (remainder == 0){
            result.push_back(combination);
            return;
        }
        if (tempLen >= len) {
            return;
        }
        int pre = -1; // 记录前一个数，去重复
        
        for (int i = tempLen; i < len; ++i) {
            if (pre == temAndidates[i]){
                continue;
            }
            if (remainder < temAndidates[i]){
                return;
            }
            pre = temAndidates[i];
            combination.push_back(temAndidates[i]);
            dfs(combination, remainder - temAndidates[i], i + 1); // i + 1代表下一个元素
            combination.pop_back();
        }
    }
    
    int len;
    vector<int> temAndidates;
    vector<vector<int> > result;
};

唠叨
用电力猫组网真是不讨好的事，电力猫容易坏，还贵，好几天没上网了，上不到网就像战士没枪的感觉，只不过还好，能看书。