当前位置:网站首页>Interview must brush algorithm top101 backtracking article top34
Interview must brush algorithm top101 backtracking article top34
2022-07-06 00:49:00 【A thief who surrendered himself】
A combination containing a collection of repeating elements
Title source :(leetcode)[https://leetcode.cn/problems/4sjJUc/]
1、 Title Description
Given an array of integers that may have duplicate numbers candidates And a target number target , find candidates All can make numbers and target The combination of .
candidates Each number in can only be used once in each combination , A solution set cannot contain duplicate combinations .
2、 Thinking analysis
Train of thought :DFS
The output data of the example is ordered, so the first thing is to sort the data , Then call DFS Recursive traversal of functions produces every result that appears there , When the condition is met, it will be added to the result array , But there is a problem because it contains repeated arrays , Therefore, repeated arrays are bound to appear in structural data , So it's going to be heavy ,find If the function cannot be found, it will be inserted into the data, but because it needs to be judged every time it is inserted into the array, the time complexity increases .
Train of thought two : to flash back + recursive
We use it dfs( pos,rest) Represents a recursive function , among pos Indicates that we are currently recursive to the array candidates No pos Number , and rest We also need to choose and for rest Put the number of into the list as a combination ;
For the current second pos Number , We can do it two ways : Choose or not . If we choose this number , So we call dfs(pos+ 1, rest - candidateslpos) Recursion , Note that there must be rest ≥ candidates[pos). If we don't choose this number , So we call dfs(pos+ 1, rest) Recursion ;
Before a recursion begins , If rest The value of is 0, That means we found a sum for target The combination of , Put it in the answer . Before each call to a recursive function , If we choose that number , You need to put it at the end of the list , This list stores all the numbers we selected . In backtracking , If we choose that number , To remove it from the end of the list .
3、 Code implementation
class Solution {
public:
void func(vector<vector<int>> &v,vector<int>&vm,int &&sum,
vector<int>&nums,vector<int> num,int target,int &&index){
if(sum>=target){
if(sum==target){
if(find(v.begin(),v.end(),vm)==v.end()){
v.push_back(vm);
}
}
return;
}
for(int i=index;i<nums.size();i++){
if(num[i]==0){
num[i]=1;
vm.push_back(nums[i]);
func(v,vm,sum+nums[i],nums,num,target,i+1);
num[i]=0;
vm.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>> v;
vector<int> vs;
vector<int> num(candidates.size(),0);
int inex=0;
func(v,vs,0,candidates,num,target,0);
return v;
}
};
class Solution {
private:
vector<pair<int, int>> freq;
vector<vector<int>> ans;
vector<int> sequence;
public:
void dfs(int pos, int rest) {
if (rest == 0) {
ans.push_back(sequence);
return;
}
if (pos == freq.size() || rest < freq[pos].first) {
return;
}
dfs(pos + 1, rest);
int most = min(rest / freq[pos].first, freq[pos].second);
for (int i = 1; i <= most; ++i) {
sequence.push_back(freq[pos].first);
dfs(pos + 1, rest - i * freq[pos].first);
}
for (int i = 1; i <= most; ++i) {
sequence.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
for (int num: candidates) {
if (freq.empty() || num != freq.back().first) {
freq.emplace_back(num, 1);
} else {
++freq.back().second;
}
}
dfs(0, target);
return ans;
}
};
Full Permutation without duplicate element set
Title source :leetcode
1、 Problem description :
Given an array of integers without duplicate numbers nums
, Back to its All possible permutations . Sure In any order Return to the answer .
2、 Thinking analysis
Careful observation shows that , The problem of finding different full permutations can be accomplished by exchanging array elements ;
If the array length is n, Exchange the first element with each subsequent element separately , Generate n Different full permutations ; Then the second element is exchanged with each subsequent element , Generate n -1 Different full permutations
3、 Code implementation
class Solution {
public:
void func(vector<vector<int>> &v,vector<int> &vm,vector<int>&nums,vector<int>&num){
if(vm.size()==nums.size()){
v.push_back(vm);
return;
}
for(int i=0;i<nums.size();i++){
if(num[i]==0){
num[i]=1;
vm.push_back(nums[i]);
func(v,vm,nums,num);
vm.pop_back();
num[i]=0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> v;
vector<int> vm;
vector<int>num(nums.size(),0);
func(v,vm,nums,num);
return v;
}
};
边栏推荐
- curlpost-php
- Zhuhai laboratory ventilation system construction and installation instructions
- Natural language processing (NLP) - third party Library (Toolkit):allenlp [library for building various NLP models; based on pytorch]
- Installation and use of esxi
- Model analysis of establishment time and holding time
- China Taiwan strategy - Chapter 8: digital marketing assisted by China Taiwan
- notepad++正則錶達式替換字符串
- After Luke zettlemoyer, head of meta AI Seattle research | trillion parameters, will the large model continue to grow?
- DD's command
- Introduction of motor
猜你喜欢
MIT doctoral thesis | robust and reliable intelligent system using neural symbol learning
Uniapp development, packaged as H5 and deployed to the server
Date类中日期转成指定字符串出现的问题及解决方法
Questions about database: (5) query the barcode, location and reader number of each book in the inventory table
anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
VSphere implements virtual machine migration
数据分析思维分析方法和业务知识——分析方法(三)
Multithreading and high concurrency (8) -- summarize AQS shared lock from countdownlatch (punch in for the third anniversary)
Classic CTF topic about FTP protocol
MySQL storage engine
随机推荐
Starting from 1.5, build a micro Service Framework - call chain tracking traceid
STM32按键消抖——入门状态机思维
Kotlin core programming - algebraic data types and pattern matching (3)
Yolov5、Pycharm、Anaconda环境安装
小程序技术优势与产业互联网相结合的分析
程序员成长第九篇:真实项目中的注意事项
Analysis of the combination of small program technology advantages and industrial Internet
Leetcode 44 Wildcard matching (2022.02.13)
The population logic of the request to read product data on the sap Spartacus home page
LeetCode 斐波那契序列
esxi的安装和使用
NLP basic task word segmentation third party Library: ICTCLAS [the third party library with the highest accuracy of Chinese word segmentation] [Chinese Academy of Sciences] [charge]
View class diagram in idea
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
curlpost-php
FFmpeg抓取RTSP图像进行图像分析
Folding and sinking sand -- weekly record of ETF
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
XML Configuration File
MYSQL GROUP_ The concat function realizes the content merging of the same ID