算法练习-day21

回溯算法

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;
    }