[回溯法]leetcode216：组合总和 Ⅲ (medium)

组合总和 Ⅲ (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);}}
};