40. Combination Sum II

本题要求相比I多了一个要求，数组里的数字在一个solution里只能至多出现一次。于此同时，我们要考虑candidate里出现重复的数字时怎么处理的情况。原则是，要使用一个数，只有当前面的相同的值的数都用了的时候才能用。这样便可以避免因为candidate里有重复的数字导致res里有重复的solution的情况。

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/19.
//  Copyright © 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int>solution;
        vector<vector<int>>res;
        
        vector<bool>inUse;
        int size = (int)candidates.size();
        for (int i = 0; i<size; i++)
        {
            inUse.push_back(false);
        }
        
        
        int level = 0;
        int sum = 0;
        
        sort(candidates.begin(), candidates.end());
        
        recursionPart(candidates, target, level, sum, solution, res, inUse);
        
        return res;
    }
    
private:
    /**
     *用于确定当前这个数是否可以使用
     */
    bool canuse( vector<bool>& inUse, vector<int>& candidates, int currentIndex)
    {
        if (currentIndex == 0)
        {
            return true;
        }
        
        // currentIndex >= 1
        if (candidates[currentIndex] != candidates[currentIndex])
        {
            return true;
        }
        
        int temp = currentIndex - 1;
        while (true)
        {
            if (temp < 0)
            {
                break;
            }
            
            if (candidates[temp] == candidates[currentIndex])
            {
                if (inUse[temp] == true)
                {
                    temp --;
                    continue;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return true;
            }
        }
        
        return true;
    }
    
    /**
     *返回值决定是否上一层递归要直接Break
     */
    bool recursionPart(vector<int>& candidates, int target, int level, int sum, vector<int>& solution, vector<vector<int>>& res, vector<bool>& inUse)
    {
        if (sum > target)
        {
            return true;
        }
        else if (sum == target)
        {
            
//            for (vector<int>::iterator it = solution.begin(); it != solution.end(); it++)
//            {
//                printf("%d ", *it);
//            }
//            printf("\n");
            res.push_back(solution);
            return true;
        }
        
        for (int i = level; i < candidates.size(); i++)
        {
            
            if(canuse(inUse, candidates, i))
            {
                sum += candidates[i];
                solution.push_back(candidates[i]);
                inUse[i] = true;
                bool isBreak = recursionPart(candidates, target, i + 1, sum, solution, res, inUse);
                
                sum -= candidates[i];
                solution.pop_back();
                inUse[i] = false;
                if (isBreak) {
                    break;
                }
            }
            
        }
        
        return false;
    }
};