如何通过算法练习-day21掌握长尾词的运用技巧？

本文共计1095个文字，预计阅读时间需要5分钟。

回溯算法 + 77. 组合 + 题意：给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。

示例：+ 思路：本题的思路主要是利用回溯的思想，先固定一个数tmp，然后递归地寻找剩余的k-1个数的组合。每次递归时，tmp的值从1开始，直到小于等于n。

+ 代码示例：pythondef combine(n, k): def backtrack(start, path): if len(path)==k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) backtrack(i + 1, path) path.pop()

result=[] backtrack(1, []) return result

回溯算法

77. 组合

题意：给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按任何顺序返回答案。

示例：

思路：本题的思想，主要是利用回溯的思想，先固定tmp插入的个数为k，当检测到tmp的大小等于k时，直接加入到我们的存储组合数组arr中，这时回溯一趟的结束条件；然后是遍历过程，定义一个起始位置，加入组合中，递归函数，不断添加新的元素进入组合中，再插入arr中，插入完一次，说明最后一个元素使用结束，移除在加入下一个元素，重复循环，直到所有组合存储完毕，返回arr

C++代码：

vector<vector<int>> arr; vector<int> tmp; void ComArr(int n,int k,int begin) { if(tmp.size()==k) { arr.push_back(tmp); return; } for(int i=begin;i<=n;i++) { tmp.push_back(i); ComArr(n,k,i+1); tmp.pop_back(); } } vector<vector<int>> combine(int n, int k) { ComArr(n,k,1); return arr; }

216. 组合总和 III

题意：找出所有相加之和为n 的k个数的组合，且满足下列条件：

1. 只使用数字1到9
2. 每个数字最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例：

思路：本题和上一道题的思路几乎一模一样，只是有两点不同：

1. 组合数的范围在1到9之间，并不是1到n
2. 每次回溯终止条件，只要满足tmp的大小等于k就必须返回，无论数组和是否等于n

C++代码：

vector<vector<int>> arr; vector<int> tmp; int SumArr(vector<int> ss)//对数组进行累加 { int sum=0; for(auto e:ss) { sum+=e; } return sum; } void ComSumArr(int k,int n,int begin) { if(tmp.size()==k)//回溯终止条件，无论数组和是否等于n，都必须返回；等于n，先插入arr中，再返回 { if(SumArr(tmp)==n) { arr.push_back(tmp); } return; } for(int i=begin;i<=9;i++)//严格限制组合数的范围 { tmp.push_back(i); ComSumArr(k,n,i+1); tmp.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { ComSumArr(k,n,1); return arr; }

17. 电话号码的字母组合

题意：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例：

思路：本题的思路就是先列举出每个数字对应的字母集合，然后将数字对应的第一个字母写入集合中，直到最后一个数字，才开始进行回溯算法，就像二叉树的后序遍历一样，从叶子开始一个个组合，再到上一层，这样循环组合

C++代码：

string sum[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//这里对应了0~9数字的字母 vector<string> arr; string tmp; void ComStrArr(string digits,int begin) { if(tmp.size()==digits.size())//只要tmp大小等于digits大小，就说明可以存入了 { arr.push_back(tmp); return; } int Num=digits[begin]-'0'; string SumNum=sum[Num];//将一个数字对应的字母集合对应起来 for(int i=0;i<SumNum.size();i++)//开始回溯组合 { tmp.push_back(SumNum[i]); ComStrArr(digits,begin+1); tmp.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits.size()==0) { return arr; } ComStrArr(digits,0); return arr; }