Buckle exercise - 35 combination sum II

35 Combinatorial summation II

1. Problem description
Given an array candidates And a target number target , find candidates All can make numbers and target The combination of , Number of output combinations .

candidates Each number in can only be used once in each combination .

explain ：

All figures （ Include target number ） Positive integers .

A solution set cannot contain duplicate combinations .

Example 1:

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

The solution set is :

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

Output ：4

Example 2:

Input : candidates = [2,5,2,1,2], target = 5,

The solution set is :

[

[1,2,2],

[5]

]

Output ：2

The following can be used: main function ：

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. Enter description
First type candidates Length of array n,

Then input n It's an integer , Space off .

Last input target .

1 <= n <= 60

1 <= candidates[i] <= 100 candidates There are duplicates of elements in .

1 <= target <= 100

3. The output shows that
Output an integer
4. Example
Input
5
2 5 2 1 2
5
Output
2
5. Code

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

//1. Search backtracking , For candidates Array , use idx Indicates the index of the currently traversed array , Array combine Used to represent the combined list ,ans Used to return the final result , At present there are target Need combination 
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int index) {
    
	int back=0;
	// Termination conditions 1: Need to be combined target Have been to 0
	if (target == 0) {
    
		ans.push_back(combine);
		return;
	}
    // Termination conditions 2： After accessing all arrays  // There may be cases where the last element after the sequence is a combination , Avoid omitting this situation 
	if (index == candidates.size()) {
        // Be careful , The judgment condition here must be placed on target==0 Back ！！！
		return;
	}

	for (int i = index; i < candidates.size(); i++)
	{
    
		if (candidates[i] <= target)
		{
    
			//  Judge whether the newly added element is equal to the last fallback element 
			   /* **  The principle here lies in the following dfs()index The parameter is i+1, After the last recursive return , **  Because after sorting , Of the caller index It may point to the same value as the element being rolled back , Repeat the result , Such as ： **  In the example [1,1,2,5,6,7,10],target=8 Example （ Let's assume that sort After that ） in , **  When index = 0 when , It's already matched [1,2,5] Result , When the call is finally traced （ That is, the first call ） after , **  Iterate to index = 1 when , The value at this position is still 1, And because of ascending sort , If not at this time index=1 exclude , **  Then it can still match another one with the subsequent elements [1,2,5] Result . */
			if (candidates[i] == back) {
    // Skip the same element as the last time 
				continue;
			}
			combine.emplace_back(candidates[i]);// Push 
			dfs(candidates, target - candidates[i], ans, combine, i + 1);// Backtracking operations 
			back = combine.back();// Access the top element of the stack 
			combine.pop_back();// eject 
		}
		else
			break;
	}
}


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

	vector<vector<int>> ans;// Result array 
	vector<int> combine;// Lists that have been combined 
	sort(candidates.begin(), candidates.end());// Ascending order 
	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;

}