216.组合总和III

函数参数：

全局变量：一维数组path，二维数组result, int sum

参数：k,n,starti

终止条件：

if(path.size()==k)

        {

            if(sum==n)

                result.push_back(path);

            return;

        }

单层逻辑：sum和path进行回溯

for(int i=starti;i<=9;i++)

        {

            sum+=i;

            path.push_back(i);

            backtracking(k,n,i+1);

            path.pop_back();

            sum-=i;

        }

对9进行剪枝，如果n小于9则没必要取到数值9，因此min(9,n)

看视频：

剪枝：

1. 如果sum已经大于targetsum（n）就可以返回了

2. 最多需要元素为9-(k-path.size())+1

17.电话号码的字母组合

思路：

先排除digit为空的情况，再将string转化成数组（反转），然后再进行回溯。

int numbers=stoi(digits);

函数参数：

全局变量：vector<string> result; string path; vector<int>nums;

终止条件：

if(path.size()==nums.size())

        {

            result.push_back(path);

            return;

        }

单层逻辑：

注意7和9有四个元素，7以后元素要加1，每次新的数组元素没有要剔除的前值，因此是backTracking(nums,i+1,beginj);

for(int i=begini;i<nums.size();i++)

        {

            //初始化endj

            int endj=3;

            if(nums[i]==7 || nums[i]==9)

                endj=4;

            for(int j=beginj;j<endj;j++)

            {

                //分类讨论

                if(nums[i]>7)

                    path+='a'+3*(nums[i]-2)+j+1;

                else

                    path+='a'+3*(nums[i]-2)+j;

                //下一个数组元素，j没有要剔除的元素

                backTracking(nums,i+1,beginj);

                path.pop_back();

            }

        }

但不知道如何剪枝。

看视频后：

1. 字符串转化：nums.push_back(digits[i]-'0');

2. 数字和字母如何映射：可以使用map或者定义一个二维数组

没有剪枝。