当前位置：首页 > article >正文

组合总数||| 电话号码的字母组合

article 2025/3/26 0:32:50

1.找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum,int Sum,int k,int startindex)
{
   if(Sum>targetSum)
   return;
   if(path.size()==k)
   {
       if(Sum==targetSum)
       result.push_back(path);
   }
   for(int i=startindex;i<=9-(k-path.size())+1;i++)
   {
       path.push_back(i);
       Sum+=i;
       backtracking(targetSum,Sum,k,i+1);
       Sum-=i;
       path.pop_back();
   }
}
vector<vector<int>> combine(int targetSum,int k)
{
    path.clear();
    result.clear();
    backtracking(targetSum,0,k,1);
    return result;
}
int main()
{
    vector<vector<int>> t=combine(9,3);
    for(const auto& n:t)
    {
        for(int m:n)
        {
            cout<<m<<" ";
       }
       cout<<endl;
   }
    return 0;
}

思路：这里仍然考察的是回溯算法，其实方法和之前类似题差不多，依然需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。

接下来还需要如下参数：

targetSum（int）目标和，也就是题目中的n。

k（int）就是题目中要求k个数的集合。

sum（int）为已经收集的元素的总和，也就是path里元素的总和。

startIndex（int）为下一层for循环搜索的起始位置。

对于终止条件，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。

所以如果path.size() 和 k相等了，就终止。如果此时path里收集到的元素和（sum）和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。

另外这里也用到了剪枝操作，为的是防止2种不必要的情况，1.当startindex指向的位置后面的数值量不足k个时 2.当Sum的值大于targetSum但数值量小于k时。

2.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

#include <bits/stdc++.h>
using namespace std;
const string LetterMap[10]={
   "",//0
   "",//1
   "abc",//2
   "def",//3
   "ghi",//4
   "jkl",//5
   "mno",//6
   "pqrs",//7
   "tuv",//8
   "wxyz",//9
};
string s;
vector<string> result;
void backtracking(const string& digits,int index)
{
   if(index==digits.size())
   {
       result.push_back(s);
       return ;
   }
   int digit=digits[index]-'0';
   string letter=LetterMap[digit];
   for(int i=0;i<letter.size();i++)
   {
       s.push_back(letter[i]);
       backtracking(digits,index+1);
       s.pop_back();
   }

}
vector<string> combine(string digits)
{
   s.clear();
   result.clear();
   if(digits.size()==0)
   return result;
   backtracking(digits,0);
   return result;
}
int main()
{
   string str="23";
   vector<string> t=combine(str);
   for(const string& c: t)
   {
       for(char m:c)
       {
           cout<<m<<" ";
       }
       cout<<endl;
   }
   return 0;
}

思路：这道题我们使用回溯算法，首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量依然定义为全局变量。这里参数digits指的是传进来的字符串（其实是数字按键），index用于遍历字符串。确定的终止条件，例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。那么终止条件就是如果index 等于输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。然后收集结果，结束本层递归。之后确定单层遍历逻辑，首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。然后for循环来处理这个字符集。

查看全文

http://www.kler.cn/a/597683.html