本节，我们将总结LeetCode组合相关的题。
这些题有很多相似的地方，回溯，剪枝，dfs等等，题目如下：
通性很多，掌握了一种，其他的就能触类旁通。
组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
这个题典型的回溯法，给出一个起始位置 i，如果满足条件进行继续递归下一个元素，这里的下一个元素有可能是 i+1，也有可能是 i，取决于具体的问题，这在之后的题目中有所体现。如果满足条件结束本次递归，回溯，因为我们没有找到所有问题的解，所以需要回到之前的位置，继续递归。
具体如下：
class Solution {
public:
int n;
int k;
vector<int> path;
vector<vector<int>> res;
vector<vector<int>> combine(int n, int k) {
this->n=n;
this->k=k;
dfs(1);
return res;
}
void dfs(int start){
if(path.size()==k){
res.push_back(path);
}
for(int i=start;i<=n;i++){
//添加
path.push_back(i);
dfs(i+1);
//回溯
path.pop_back();
}
}
};
上题稍微改编，可以得到全排列这个题。
全排列
给定一个 没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这个稍微改变了一些，在搜索过程需要知道当前元素是否被访问过，为了高效地了解该元素是否被访问，我们可以使用set。
具体如下：
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
set<int> visted;
vector<vector<int>> permute(vector<int>& nums) {
fun(nums);
return res;
}
void fun(vector<int>& nums){
//满了，为一个合适的路径
if(path.size()==nums.size()){
res.push_back(path);
}
for(int num:nums){
//num未被访问
if(visted.find(num)==visted.end()){
path.push_back(num);
visted.insert(num);
fun(nums);
visted.erase(num);
path.pop_back();
}
}
}
};
这个题也可以有另一种标记方法，当我们访问到一个元素时，我们将其与起始搜索元素进行替换，这样往下搜索的元素是没有被访问过的了，回溯时，又交换一次，还原数组。
class Solution {
public:
vector<vector<int>> res;
int len;
vector<vector<int>> permute(vector<int>& nums) {
len=nums.size();
dfs(nums,0);
return res;
}
void dfs(vector<int>& nums,int start){
if(start==len){
res.push_back(nums);
}
for(int i=start;i<len;i++){
//swap
swap(nums[i],nums[start]);
dfs(nums,start+1);
//回溯
swap(nums[i],nums[start]);
}
}
};
接下来我们看看组合总和这四个题。
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
这个题需要注意的便是可以重复使用数字，意味当从当前位置 i 进行搜索时，下一次的搜索可以从 i 继续开始。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(candidates,target,0);
return res;
}
void dfs(vector<int>& candidates,int target,int start){
if(target==0){
res.push_back(path);
return ;
}
for(int i=start;i<candidates.size();i++){
if(target>=candidates[i]){
path.push_back(candidates[i]);
//可以重复使用数字
dfs(candidates,target-candidates[i],i);
path.pop_back();
}
}
}
};
组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
每个数字只能使用一次，那么我们可以从上一题出发，将下一次搜索的位置设为 i+1。
但这样会有一个问题，会搜索到重复的组合，这种现象是因为原数组中有重复的元素，比如说和6，数组为2，2，4...。在以第一个2为起点，[2,4]是一个组合，以下一个2为起点时，[2,4]也是一个组合，但重复了。
如果我们想用这种方法来做的话，可以使用map去重。
class Solution {
public:
vector<int> path;
map<vector<int>,int> m;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(candidates,target,0);
vector<vector<int>> res;
for(auto b=m.begin();b!=m.end();b++){
res.push_back(b->first);
}
return res;
}
void dfs(vector<int>& candidates,int target,int start){
if(target==0){
m[path]++;
return ;
}
for(int i=start;i<candidates.size();i++){
if(target>=candidates[i]){
path.push_back(candidates[i]);
//不能重复使用数字
dfs(candidates,target-candidates[i],i+1);
path.pop_back();
}
}
}
};
当然，一种更好的方法是增加剪枝过程，对于重复的情况只进行一次搜索。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(candidates,target,0);
return res;
}
void dfs(vector<int>& candidates,int target,int start){
if(target==0){
res.push_back(path);
return ;
}
for(int i=start;i<candidates.size();i++){
//剪枝
if(target<candidates[i]){
return ;
}
if(i>start&&candidates[i-1]==candidates[i]){
continue;
}
path.push_back(candidates[i]);
dfs(candidates,target-candidates[i],i+1);
path.pop_back();
}
}
};
组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
这个题增加了组合的个数，那我们只要增加对组合长度的判断即可。
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k,n,1);
return res;
}
void dfs(int k,int n,int start){
if(k==0&&n==0){
res.push_back(path);
return ;
}
for(int i=start;i<=9;i++){
path.push_back(i);
dfs(k-1,n-i,i+1);
path.pop_back();
}
}
};
组合总和 IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？
这个题稍微有了一些改变，一种方法是使用背包的思想，对于背包问题，Acwing上有背包一系列的问题，之后我会总结背包的各种问题。
方法是动态规划。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,0);
dp[0]=1;
for(int i=0;i<=target;i++){
for(int j=0;j<nums.size();j++){
if(i>=nums[j]){
dp[i]=(dp[i]>=(INT_MAX-dp[i-nums[j]]))?INT_MAX:dp[i]+dp[i-nums[j]];
}
}
}
return dp[target];
}
};
另一种方法是增加剪枝过程，和之前的题略有不同。
class Solution {
public:
long long sum;
vector<long long> tmp;
int combinationSum4(vector<int>& nums, int target) {
tmp=vector<long long> (target+1,-1ll);
for(int i=1;i<=target;i++){
sum=0;
dfs(nums,i);
tmp[i]=sum;
}
return sum;
}
void dfs(vector<int>& nums,int target){
if(target<0){
return ;
}
if(tmp[target]!=-1){
sum+=tmp[target];
sum%=INT_MAX;
return ;
}
if(target==0){
sum++;
return ;
}
for(int i=0;i<nums.size();i++){
dfs(nums,target-nums[i]);
}
}
};
组合相关的题还有不少，之后会继续更新相关的题。
网友评论