力扣hot100 —— 电话号码字母组合； 子集 （非回溯做法）简单易懂

由于博主对回溯也不是很熟悉，这里提出一种简单易懂的解法（有点暴力）

解题思路：

每个数字对应有自己的字母串；

首先遍历将每个字母存入也就是 res{{a},{b},{c}}

然后遍历后续数子对应的字母，让每个字母与当前res中·元素组合然后更新进去

res{{ad},{bd},{cd},{ae},{be},{ce},{af},{bf},{cf}}

class Solution {
public:
    vector<string> base{" ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    vector<string> letterCombinations(string digits) {
        // 暴力解法，逐渐添加，组合
        vector<string> res;
        if (digits.empty()) {
            return res; // 如果输入为空，直接返回空结果
        }
        res.push_back(""); // 初始化结果，加入一个空字符串
        for (auto &digit : digits) {
            int dig_num = digit - '0'; // 将字符数字转为整数
            string chars = base[dig_num - 1]; // 获取当前数字对应的字符集
            vector<string> newRes; // 用于存储新的组合
            for (auto &s : res) {
                for (auto &ch : chars) {
                    newRes.push_back(s + ch); // 将当前字符与已有组合拼接
                }
            }
            res = newRes; // 更新结果
        }
        return res;
    }
};

解法思路：与字母组合类似，只是这里不用更新结果；逐渐将每次组合加入就行

（nums = [1, 2, 3, 4], ans = [[ ]], 下标 i 从 0 开始）

1. ans = [[ ]], nums[0] = 1, 将元素1和ans内所有子集组合并添加进ans

此时：ans = [[ ], [1]]；

2. ans = [[ ], [1]], nums[1] = 2, 将元素2和ans内所有子集组合并添加进ans

此时：ans = [[ ], [1], [2], [1, 2]]；

3. ans = [[ ], [1], [2], [1, 2]], nums[2] = 3, 将元素3和ans内所有子集组合并添加进ans

此时：ans = [[ ], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]；

3. ans = [[ ], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]], nums[3] = 3, 将元素3和ans内所有子集组合并添加进ans

此时：ans = [[ ], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]；

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // 组合添加，空集也算子集
        // 遍历数字，每个数子与当前结果中的数据组合，然后添加进去
        vector<vector<int>> res;
        res.push_back({});
        for(auto &num : nums){
            vector<int> temp; // 暂存当前结果中的元素， push_back是void 类型不会直接改变
            int sub_size = res.size();
            for(int i= 0; i<sub_size;i++){ // 获取当前子集进行组合
                temp = res[i];
                temp.push_back(num);
                res.push_back(temp);
            }
        }
        return res;
    }

};