Buckle practice - sum of 34 combinations

34 Combinatorial summation

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

candidates The number in can be selected repeatedly without limit .

explain ：

All figures （ Include target） Positive integers .

A solution set cannot contain duplicate combinations .

Example 1：

Input ：candidates = [2,3,6,7], target = 7,

The solution set is ：

[

[7],

[2,2,3]

]

Output ：2

Example 2：

Input ：candidates = [2,3,5], target = 8,

The solution set is ：

[

[2,2,2,2],

[2,3,3],

[3,5]

]

Output ：3

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().combinationSum(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 <= 30

1 <= candidates[i] <= 100 candidates Each element in is unique .

1 <= target <= 100
3. The output shows that
Output an integer
4. Example
Input
3
2 3 5
8
Output
3
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) {
    

	//1. Termination conditions 1： After accessing all arrays 
	if (index == candidates.size()) {
    
		return;
	}
	//2. Need to be combined target Have been to 0
	if (target == 0) {
    
		ans.push_back(combine);
		//ans.emplace_back(combine);// List that has been combined combine Insert into ans
		//push_back() Method to call the constructor and copy constructor , First construct a temporary object , And then put the temporary copy Constructor copies or moves to the back of the container .
		//emplace_back() At the time of implementation , This element is created directly at the end of the container , It eliminates the process of copying or moving elements .
		return;
	}
	//  Directly skip the currently traversed element , Skip to the next element 
	dfs(candidates, target, ans, combine, index + 1);
	//  Select the currently traversed element 
	if (target - candidates[index] >= 0) {
    
		combine.emplace_back(candidates[index]);
		dfs(candidates, target - candidates[index], ans, combine, index);// Backtracking process 
		combine.pop_back();// Pay attention to the operation here 
	}
}


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

	vector<vector<int>> ans;// Result array 
	vector<int> combine;// Lists that have been combined 
	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;

}