国家工程建设信息网站,汕头模板建站代理,接做网站简介,域名服务器作用1.全排列 全排列 II
1.给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
2.给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。
示例 1#xff1a;
输入#xff1a;nums [1,2,3…1.全排列 全排列 II
1.给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
2.给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10
分析是回溯的全排列类型刚开始写的时候传参传的不是used的地址所以used里面持续是0
#include bits/stdc.h
using namespace std;
vectorint nums;
vectorint path;
vectorbool used(nums.size(),false);
void f(vectorint nums,vectorbool used)
{if(nums.size()path.size()){for(int i0;ipath.size();i) coutpath[i] ;coutendl;return;}for(int i0;inums.size();i){if(used[i] true) continue;used[i]true;path.push_back(nums[i]);f(nums,used);path.pop_back();used[i]false;}
}
main()
{int x;while(cinx){nums.push_back(x);}f(nums,used);
}分析这个剪枝不是很好理解if(nums[i]nums[i-1] used[i-1] false) continue;这里是对同一层进行剪枝同一层表示的是同一个位置如果这个位置上的数重复了那我们就直接continue
#include bits/stdc.h
using namespace std;
vectorint nums;
vectorint path;
vectorbool used(nums.size(),false);
void f(vectorint nums,vectorbool used)
{if(nums.size()path.size()){for(int i0; ipath.size(); i) coutpath[i] ;coutendl;return;}for(int i0; inums.size(); i){if(nums[i]nums[i-1] used[i-1] false) continue;if(used[i]false){used[i]true;path.push_back(nums[i]);f(nums,used);path.pop_back();used[i]false;}}
}
main()
{int x;while(cinx){nums.push_back(x);}sort(nums.begin(),nums.end());f(nums,used);
}2.组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]提示
1 n 201 k n
分析 这个在我看来属于回溯的组合型我打算用组合型来做
#include bits/stdc.h
using namespace std;
vectorint path;
int num[21];
int n,k;
void f(int n)
{int i,j;int dk-path.size();if(path.size()k){for(i0;ik;i)coutpath[i] ;coutendl;return;}for(jn;jd-1;j--){path.push_back(j);f(j-1);path.pop_back();}
}
main()
{cinnk;f(n);
}3.子集 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2
输入nums [0]
输出[[],[0]]提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
分析这个用选和不选的类型来做思路就比较清晰了
#include bits/stdc.h
using namespace std;
vectorint path;
int num[21],n;
void f(int i,int index)
{if(in){for(int j0; jindex; j) coutpath[j] ;coutendl;return;}f(i1,index);path.push_back(num[i]);f(i1,index1);path.pop_back();
}
main()
{int x,i0;while(cinx){num[i]x;i;}ni;f(0,0);
}
