力扣练习——35 组合总和 II

35 组合总和 II

1.问题描述
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，输出组合的数量。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。

解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

输出：4

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,

所求解集为:

[

[1,2,2],

[5]

]

输出：2

可使用以下main函数：

int main()

{

int n,data,target;

vector<int> candidates;

cin>>n;

for(int i=0; i<n; i++)

{

    cin>>data;

    candidates.push_back(data);

}

cin>>target;

vector<vector<int> > res=Solution().combinationSum2(candidates,target);

cout<<res.size()<<endl;

return 0;

}
2.输入说明
首先输入candidates数组的长度n，

然后输入n个整数，以空格分隔。

最后输入target 。

1 <= n <= 60

1 <= candidates[i] <= 100 candidates 中的元素存在重复。

1 <= target <= 100

3.输出说明
输出一个整数
4.范例
输入
5
2 5 2 1 2
5
输出
2
5.代码

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

//1.进行搜索回溯，其中对于candidates数组，用idx表示当前遍历的数组下标，数组combine用来表示已经组合的列表，ans用来返回最后的结果，目前还有target需要组合
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int index) {
    
	int back=0;
	//终止条件1:需要进行组合的target已经为0
	if (target == 0) {
    
		ans.push_back(combine);
		return;
	}
    //终止条件2：访问完所有数组 //可能会有排完序后的最后那个元素是组合一员的情况，避免遗漏该情况
	if (index == candidates.size()) {
        //注意，这里这个判断条件一定要放在target==0后面！！！
		return;
	}

	for (int i = index; i < candidates.size(); i++)
	{
    
		if (candidates[i] <= target)
		{
    
			// 判断新加入的元素是否等于上次回退的元素
			   /* ** 这里的原理在于下面的dfs()index的参数是i+1，当上一次递归返回后， ** 因为经过了排序，调用者的index可能指向与回退的元素相同的值，造成结果的重复，如： ** 在例子[1,1,2,5,6,7,10]，target=8的例子（假设已经sort过了）中， ** 当index = 0时，已经配对了[1,2,5]的结果，当最后回溯到该调用（即第一个调用）后， ** 迭代到index = 1时，该位置上的值还是1，且因为升序排序，此时若不讲index=1排除， ** 则它仍可以与后续的元素再匹配出一个[1,2,5]的结果。 */
			if (candidates[i] == back) {
    //跳过和上一次相同元素的情况
				continue;
			}
			combine.emplace_back(candidates[i]);//入栈
			dfs(candidates, target - candidates[i], ans, combine, i + 1);//回溯操作
			back = combine.back();//访问栈顶元素
			combine.pop_back();//弹出
		}
		else
			break;
	}
}


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

	vector<vector<int>> ans;//结果数组
	vector<int> combine;//已经组合的列表
	sort(candidates.begin(), candidates.end());//升序排列
	dfs(candidates, target, ans, combine, 0);
	return ans;
}


int main()

{
    

	int n, data, target;

	vector<int> candidates;

	cin >> n;

	for (int i = 0; i < n; i++)

	{
    

		cin >> data;

		candidates.push_back(data);

	}

	cin >> target;

	vector<vector<int> > res = combinationSum(candidates, target);

	cout << res.size() << endl;

	return 0;

}