leetcode - 40. Combination Sum II - Medium

descrition

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.
• 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]

]

解析

和 leetcode - 39. Combination Sum - Medium 类似，只是这里的数组元素存在重复，并且元素不可重复取。

代码只实现了其中一种递归形式，这样的实现方法递归层数应该是最浅的。

code

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Solution{

public:

	vector<vector<int> > combinationSum2(vector<int> &candidates, int target){

		vector<vector<int> > ans;

		vector<int> vecCur;

		sort(candidates.begin(), candidates.end());

		combinationSum2Backtracking(candidates, 0, vecCur, target, ans);

		return ans;

	}

	void combinationSum2Backtracking(vector<int>& candidates, int index,

						             vector<int>& vecCur, int target,

						             vector<vector<int> > &ans){

		if(target < 0)

			return;

		if(target == 0){

			if(!vecCur.empty())

				ans.push_back(vecCur);

			return;

		}

		for(int i=index; i<candidates.size(); i++){

			if(candidates[i] > target) // candidates mush in ascending order

				break;

			// choose candidates[i], and each number in candidates may only

			// be used onece in combination

			vecCur.push_back(candidates[i]);

			combinationSum2Backtracking(candidates, i+1, vecCur, target - candidates[i], ans);

			// don't choose candidates[i]

			vecCur.pop_back();

			// skip the duplicate

			while((i+1)<candidates.size() && candidates[i+1] == candidates[i])

				i++;

			// after i++, i will point to a new unique number

		}

	}

};

int main()

{

	return 0;

}