# LeetCode - 0040. Combination Sum II
### 題目網址：https://leetcode.com/problems/combination-sum-ii/
###### tags: `LeetCode` `Medium` `動態規劃（Dynamic Programming）` `回溯法（Backtracking）` `深度優先搜尋（Depth First Search）`

/*
    -LeetCode format-
    Problem: 40. Combination Sum II
    Difficulty: Medium
    
    by Inversionpeter
*/



bool DP[101][31];
int combinations[31], nowAmount, nowIndex, nowValue;
map <vector<int>, bool> haveKind;
vector <vector <int>> answer;
vector <int> *numbers;

static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    for (int i = 0; i < 101; ++i)
        DP[i][0] = 1;
    return nullptr;
}();

class Solution {
    
    static void PushAnswer() {
        vector <int> subset(nowAmount);
        for (int i = 0; i < nowAmount; ++i)
            subset[i] = combinations[nowAmount - i - 1];
        if (haveKind.find(subset) == haveKind.end()) {
            answer.push_back(subset);
            haveKind[subset] = true;
        }
    }
    
    static void Backtrack() {
        if (nowIndex < 0 || nowValue < 0 || !DP[nowIndex + 1][nowValue])
            return;
        --nowIndex; Backtrack(); ++nowIndex;
        nowValue -= (*numbers)[nowIndex];
        combinations[nowAmount] = (*numbers)[nowIndex]; ++nowAmount;
        if (nowValue) {
            --nowIndex; Backtrack(); ++nowIndex; 
        }
        else
            PushAnswer();
        nowValue += (*numbers)[nowIndex]; --nowAmount;
    }
    
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        answer.clear(); haveKind.clear();
        for (int i = 0; i != candidates.size(); ++i) {
            for (int j = 1; j <= target; ++j)
                DP[i + 1][j] = DP[i][j];
            for (int j = target; j >= candidates[i]; --j)
                DP[i + 1][j] |= DP[i + 1][j - candidates[i]];
        }
        numbers = &candidates;
        nowIndex = candidates.size() - 1; nowValue = target;
        Backtrack();
        return answer;
    }
};