题目描述:
给定一个无重复元素的数组 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]
]
要完成的函数:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
说明:
1、这道题给定一个vector,里面装着彼此不重复的元素,元素是正整数,还给了一个target,也是正整数。
要求找出各种有可能的组合,使得vector中的元素的和等于target。
每个组合存储在一个一维的vector中,最终把这些一维的vector存在二维的vector中,返回二维vector。
各个组合不能重复。
2、我们先来看一个例子,vector是[2,3,6,7],target是7,我们人类怎么解决这个问题呢?
我们当然是从后面看起,最大的7,看能不能满足target,结果是可以的,那么我们再看前一个数6。
6小于等于7,我们还要一个1,往本身或者前面看有没有小于等于1的,结果没有,那么我们就没有办法搭配6了,我们再看前一个数3。
3小于等于7,我们还要4,本身还可以再减去3,那么还要一个1,再往本身或者前面看,没有1。
那我们也许可以不要第二次减去3,我们减去前一个数2,然后还要一个2,刚好本身可以满足。
然后再看前一个数2,本身还可以再减去2,然后本身还可以再减去2,然后还要一个1,但没有办法了。
所以最终我们得到的组合是[[7],[3,2,2]]。
做的题目比较多的同学,可能已经嗅到了一股递归的味道。
这道题就是要不断试探,试探可以满足target的,插入到二维vector中,试探到不可以满足的,回退一步,再试其他可能。
代码如下:(附详解)
vector<vector<int>>res;//全局变量,最终要返回的二维vector
vector<int>res1;//全局变量,存储每次可能的组合结果
void digui(vector<int>& candidates,int index,int target,vector<int>& res1)
{
if(target==0)//退出条件
{
res.push_back(res1);//存储到二维vector中
return;
}
while(index>=0)//不断地试探
{
if(candidates[index]<=target)//如果可以减去
{
res1.push_back(candidates[index]);//进入递归前,设置一下res
digui(candidates,index,target-candidates[index],res1);
res1.pop_back();//退出递归,恢复一下res
}
index--;//index-1,试探前一个数值
}
if(index<=0)//如果index==-1,那么只能返回了
return; }
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
int s1=candidates.size();
digui(candidates,s1-1,target,res1);//直接进入递归
return res;
}
上述代码在递归那个部分,可能有些同学还不太清晰,可以自己手写一下推导的过程,逻辑会更加清晰。
【 再啰嗦两句,理解逻辑的同学可以不用看了】
其实vector比如[2,3,6,7],我们可以粗略地看成外层的递归和内层的递归。外层递归比如第一次试探了7,刚刚好。
接着循环迭代到前一个数6,可以减去,然后进入内层递归,不能再减去本身6了,所以循环迭代到前一个数3,也还是不能,所以循环迭代到前一个数2,也还是不能,然后结束内层递归。
接着循环迭代到前一个数3,可以减去,然后进入内层递归,可以减去本身3,再进入深一层的内层递归,不能再减去3了,循环迭代到前一个数2,也不能,结束深一层的内层递归,返回内层递归,我们不减去3,直接减去2,进入深一层的内层递归,可以减去本身2,那么结束深一层的内层递归,同时vector到头部了,结束内层递归。
接着循环迭代到前一个数2,可以减去,然后进入内层递归,可以减去本身2,进入深一层的内层递归,可以减去本身2,进入再深一层的内层递归,不能再减去2了,于是退出再深一层的内层递归,再退出深一层的内层递归,再退出内层递归。
接着……前面没有数了,结束外层递归。
我们会发现其实外层递归和内层递归的处理逻辑是一样的,都是不断地试探,所以我们可以统一写成一种形式。
上述代码实测12ms,beats 98.16% of cpp submissions。