[LeetCode] Combination Sum II

Combination Sum II

Given a collection 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] 

Solution:

int differentCandidatesNum;
int* differentCandidates;
int* differentCandidatesCount;
vector<vector<int> > ans;
int targ;


void dfs(int k, int curSum, vector<int> curCount)
{
    /*
    cout << "k = " << k << " curSum = " << curSum << endl;
    cout << "curCount: ";
    for(int i = 0;i < curCount.size();i++)
        cout << curCount[i] << " ";
    cout << endl;
    */
    if(curSum > targ) 
        return;
    if(curSum == targ)
    {
        vector<int> curCom;
        for(int i = 0;i < curCount.size();i++)
            for(int j = 0;j < curCount[i];j++)
                curCom.push_back(differentCandidates[i]);
        ans.push_back(curCom);
        return;
    }

    if(k >= differentCandidatesNum) 
        return;

    //try the k the no duplicate candidates
    //choose 0 to differentCandidatesCount[k]'s k to check if this is a good combination

    for(int i = 0;i <= differentCandidatesCount[k];i++)
    {
        curCount.push_back(i);
        dfs(k + 1, curSum + i * differentCandidates[k], curCount);
        curCount.pop_back();
    }
}


vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        if(num.size() == 0) return ans;

        //sort the candidate num
        for(int i = 0;i < num.size();i++)
        {
            bool continueBubble = false;

            for(int j = 0;j < num.size() - i - 1;j++)
            {
                if(num[j] > num[j + 1])
                {
                    int tmp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = tmp;
                    continueBubble = true;
                }
            }

            if(continueBubble == false)
                break;
        }

        //get no duplicate candidates
        int curNum = num[0], counter = 1;
        differentCandidates = new int[num.size()];
        differentCandidatesCount = new int[num.size()];
        differentCandidatesNum = 0;
        
        for(int i = 1;i < num.size();i++)
        {
            if(curNum == num[i]) 
            {
                counter++;
            }
            else
            {
                differentCandidates[differentCandidatesNum] = curNum;
                differentCandidatesCount[differentCandidatesNum] = counter;
                differentCandidatesNum++;
                counter = 1;
                curNum = num[i];
            }
        }
        //add last no duplicate candidate
        differentCandidates[differentCandidatesNum] = curNum;
        differentCandidatesCount[differentCandidatesNum] = counter;
        differentCandidatesNum++;
    //    for(int i = 0;i < differentCandidatesNum;i++)
    //        cout << differentCandidates[i] << " num = " << differentCandidatesCount[i] << endl;
        
        //begin dfs to search combinations.
        targ = target;
        vector<int> cur;
        dfs(0, 0, cur);

        delete [] differentCandidates;
        return ans;
    }