標(biāo)簽： C++ 算法 LeetCode DFS

每日算法——leetcode系列

問(wèn)題 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) {
        
    }
};

翻譯

和的組合

難度系數(shù)：中等

給定一個(gè)一些數(shù)組成的候選集合C唯鸭，和一個(gè)目標(biāo)數(shù)T∷圆猓現(xiàn)從C中選出一些數(shù)，求所有不同的取數(shù)方案使其累加和恰好等于T肿孵。
C中的每個(gè)數(shù)都只能用一次。

注意

• 所有的數(shù)（包括目標(biāo)數(shù)）都為正整數(shù)
• 組合中的元素(a1, a2, … , ak) 不能為降序排列疏魏。(ie, a1 ≤ a2 >≤ … ≤ ak)
• 不能有重復(fù)的組合方案
  例如：候選集合10,1,2,7,6,1,5 和目標(biāo)值8,
  答案為：
  [1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

思路

和Combination Sum很像停做，只是這里不能重復(fù)取一個(gè)元素，但根據(jù)例子看是元素是有重復(fù)元素的大莫。
這樣就得去重復(fù)蛉腌。

代碼

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; // 記錄前一個(gè)數(shù)，去重復(fù)
        
        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代表下一個(gè)元素
            combination.pop_back();
        }
    }
    
    int len;
    vector<int> temAndidates;
    vector<vector<int> > result;
};

嘮叨
用電力貓組網(wǎng)真是不討好的事只厘，電力貓容易壞烙丛，還貴，好幾天沒(méi)上網(wǎng)了羔味，上不到網(wǎng)就像戰(zhàn)士沒(méi)槍的感覺(jué)河咽，只不過(guò)還好，能看書(shū)赋元。