组合总和 Ⅲ (medium)"/>
[回溯法]leetcode216:组合总和 Ⅲ (medium)
题目:
题解:
- 回溯法
- 回溯法的框架题,注意判断找到一个可行解的标志是索引index与决策路径的大小相等,且决策路径的总和与n相等;若大于等于决策路径大小或sum大于n,表示我们走弯路了,需要返回上一层。还有需要注意组合中的数只能为1-9的数字,且不能重复,所以我们按顺序增长就好了,这样就不会重复了。
代码如下:
class Solution {
public://题解:回溯法vector<vector<int>> combinationSum3(int k, int n) {vector<int> track(k,0);vector<vector<int>> result;backtrack(result,track,0,0,n);return result;}//index用来表示track的索引的,索引等于track大小的话,判断是否找到可行解void backtrack(vector<vector<int>>& result,vector<int>& track,int index,int sum,int n){//找到一个可行解if(index==track.size()&&sum==n)result.push_back(track);//走到弯路,返回上一层if(index>=track.size()||sum>n)return;//确定i的初始值,索引为0的话,i的初始值为第一个值+1,主要为了避免越界int i=index-1>=0?track[index-1]+1:track[0]+1;for(;i<10;++i){//组合中只存在1-9的数字//加入决策路径track[index]=i;//进入下一步决策backtrack(result,track,index+1,sum+track[index],n);}}
};
更多推荐
[回溯法]leetcode216:组合总和 Ⅲ (medium)
发布评论