开锁在百度上做网站要钱吗,论坛网站建设规划书,赚钱平台网站,企业信息查询官网系统1.1 子集I 思路可以简单概括为 二叉树#xff0c;每一次分叉要么选择一个元素#xff0c;要么选择空#xff0c;总共有n次#xff0c;因此到n1进行保存结果#xff0c;返回。像这样#xff1a; #include cstdio
#include vector
#include algorithm每一次分叉要么选择一个元素要么选择空总共有n次因此到n1进行保存结果返回。像这样 #include cstdio
#include vector
#include algorithm
using namespace std;
int n;
vectorint temp;
vectorvectorint result;
void DFS(int m){if (m n1){result.push_back(temp);return ;}//选择元素mtemp.push_back(m);DFS(m1);//继续递归temp.pop_back();//返回//选择空DFS(m1);
}bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;
}
最后自己编写比较函数简单来说vector大小相同时可以直接按照 这些比较符号进行比较。大小不同时则按照vector大小进行排序这里按照题目要求均是小于。
1.2 子集II 区别在于自己给定一些元素进行排序。
那么只需要用一个数组存储这些元素在压栈/出栈时换成对应的数组元素即可思路一致。
代码几乎没有变化。
#include cstdio
#include algorithm
#include vector
using namespace std;
vectorint temp;
vectorvectorint result;
const int N 15;
int q[N];
int n;
void DFS(int m){if (mn1){result.push_back(temp);return ;}temp.push_back(q[m]);DFS(m1);temp.pop_back();DFS(m1);
}
bool cmp(vectorint a ,vectorint b){if (a.size()! b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);for (int i1;in;i)scanf(%d,q[i]);DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}
1.3 子集III 思路还是二叉树深搜递归但是由于会出现重复的数按照之前的输出会重复输出一些值例如样例里的1的子集都会输出两边因为代码并没有认为第一个1与第二个1是不同的。
首先输入的序列是升序的因此我们可以连续地处理这些重复的元素。
例如 2 3 3 3 5 #include cstdio
#include algorithm
#include vector
using namespace std;
vectorint temp;
vectorvectorint result;
const int N 15;
int q[N];
int n;
void DFS(int idx){if (idxn1){result.push_back(temp);return ;}int cnt1;while (idxn q[idx]q[idx1]){cnt;idx;}//经过该循环idx 最后一个重复元素的序号cnt为重复元素的个数// 选择空 DFS(idx1);//选择重复元素for (int i1;icnt;i){temp.push_back(q[idx]);DFS(idx1);// 选择重复的元素为 1 2 3 ....cnt个}//在这个循环中我们将之前添加到 temp 中的元素逐个移除//以回溯到不添加这些重复元素的情况for (int i1;icnt;i){temp.pop_back();}
}
bool cmp(vectorint a ,vectorint b){if (a.size()! b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);for (int i1;in;i)scanf(%d,q[i]);DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}
2.1 全排列I 思路很简单给个图 设置个q[]表示其是否被使用过依次递归返回时再赋值0
#include cstdio
#include algorithm
#include vector
using namespace std;
vectorint temp;
vectorvectorint result;
int n;
const int N 10;
int q[N]{0};
void DFS(int m){if (m n1){result.push_back(temp);}for (int i1;in;i){if (!q[i]){temp.push_back(i);q[i]1;DFS(m1);q[i]0;temp.pop_back();}}}
bool cmp(vectorint a ,vectorint b){if (a.size()!a.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}
2.2 全排列II 思路依旧简单全排列I是用i作为正整数这次是给定正整数压栈和出栈q[]来储存输入的数flag[]来表示其是否被使用过代码相同
#include cstdio
#include algorithm
#include vectorusing namespace std;
int n;
const int N10;
int q[N];
int flag[N] {0};
vectorint temp;
vectorvectorint result;
void DFS(int m){if (mn1){result.push_back(temp);}for (int i1;in;i){if (!flag[i]){temp.push_back(q[i]);flag[i]1;DFS(m1);flag[i]0;temp.pop_back();}}}
bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);for (int i1;in;i)scanf(%d,q[i]);DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}
2.3 全排列III 如果按照之前的思路那么样例1会出现大量重复与子集的解决方法类似不过是这里是记录每个数的个数使用cnt[]进行计算并且每个数只记录一次
1 1 3 : 只取最后一个重复的id进行记录次数像这样cnt[1] 0 cnt[2]2 cnt[3] 1
那么全排列就很简单每次的全排列对于q[i]的数只能用cnt[i]次数。
那么每次for循环 for (int i1;in;i){if (cnt[i]){temp.push_back(q[i]);cnt[i]--;DFS(m1);cnt[i];temp.pop_back();}}
只能用一次重复的值
#include cstdio
#include algorithm
#include vectorusing namespace std;
int n;
const int N 10;
int q[N];
int cnt[N]{0};
vectorint temp;
vectorvectorint result;
void DFS(int m){if (mn1){result.push_back(temp);return ;}for (int i1;in;i){if (cnt[i]){temp.push_back(q[i]);cnt[i]--;DFS(m1);cnt[i];temp.pop_back();}}
}
bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d,n);for (int i1;in;i)scanf(%d,q[i]);for (int i1;in;i){int ji;cnt[i]1;while (jn q[j]q[j1]){cnt[i];j;}i j;}DFS(1);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}
3.1 组合I 和全排列很像不过全排列是有顺序的样例中3 4 和4 3在全排列均是有效的而组合是无序的因此我们在挑选的时候可以人为地进行有序限制从而不会重复。
思路与这道递归题类似
[递归] 自然数分解之方案数_慕梅^的博客-CSDN博客
我们保证后一个数要大于前一个这样的要求那么就可实现组合题。
样例2中 两个数x y 满足xy
那我们的DFS(int m)m则是后面的数需要大于的序号
DFS(0)可以作为入口
#include cstdio
#include algorithm
#include vectorusing namespace std;
int n,k;
const int N 15;vectorint temp;
vectorvectorint result;void DFS(int m){if (temp.size()k){//递归的出口则改为vector int temp的大小kresult.push_back(temp);return ;}for (int im1;in;i){//循环从 序号m1开始temp.push_back(i);DFS(i);//将i作为参数进行下一次的递归temp.pop_back();}return ;}
bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d%d,n,k);DFS(0);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}3.2 组合II
需要自己输入序列思路不变 #include cstdio
#include algorithm
#include vectorusing namespace std;
int n,k;
const int N 15;
int q[N];
vectorint temp;
vectorvectorint result;void DFS(int m){if (temp.size()k){result.push_back(temp);return ;}for (int im1;in;i){temp.push_back(q[i]);DFS(i);temp.pop_back();}
}
bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d%d,n,k);for (int i1;in;i)scanf(%d,q[i]);DFS(0);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}3.3 组合III 可以借鉴全排列的思想使用cnt来进行计数
#include cstdio
#include algorithm
#include vectorusing namespace std;
int n,k;
const int N 15;
int q[N];
int cnt[N]{0};
vectorint temp;
vectorvectorint result;void DFS(int m){if (temp.size()k){result.push_back(temp);return ;}for (int im;in;i){//i从m开始因为有重复的元素。if (cnt[i]){cnt[i]--;temp.push_back(q[i]);DFS(i);cnt[i];temp.pop_back();}}
}
bool cmp(vectorint a,vectorint b){if (a.size()!b.size())return a.size()b.size();return ab;
}
int main(){scanf(%d%d,n,k);for (int i1;in;i)scanf(%d,q[i]);for (int i1;in;i){int j i;cnt[i] 1;while ((j1)nq[j]q[j1]){cnt[i];j;}i j;}DFS(0);sort(result.begin(),result.end(),cmp);for (int i0;iresult.size();i){for (int j0;jresult[i].size();j){if (jresult[i].size()-1)printf(%d,result[i][j]);else printf(%d ,result[i][j]);}printf(\n);}return 0;}不过与前两个组合不同的是
for (int im1;in;i){
条件因改为
for (int im;in;i){ 如果不该与之前的序列都是没有重复的元素因此可以下一次的序号需要1以保证大于前面的数然而这里有重复的元素因此从m开始。
