最简单的“栗子”

一个袋子里有字母“A，B，C”，另一个袋子里有数字“1，2，3”，从每一个袋子里摸一个出来。

#include <iostream>
#include <string>
using namespace std;
string let = "ABC";
string num = "123";
string res ="xx";
void dfs(int level){
    if(level == 2) {
        cout <<"res == "<< res <<endl;
        return;
    }
    if(level == 0){
        for(char c : let){
            res[level] = c;
            dfs(level+1);
        }
    }
   if(level == 1){
        for(char c : num){
            res[level] = c;
            dfs(level+1);
        }
    }
}
int main(){
    dfs(0);
   return 0;
}

level == 0和level == 1的时候的操作都是一致的，只是拥有的选择不一样，所以可以合并起来

#include <iostream>
#include <string>
using namespace std;
string let = "ABC";
string num = "123";
string res ="xx";
void dfs(int level){
    if(level == 2) {
        cout <<"res == "<< res <<endl;
        return;
    }
    string choose = level == 0 ? let : num;
    for(char c : choose){
        res[level] = c;
        dfs(level+1);
    }

}
int main(){
    dfs(0);
   return 0;
}

如果不仅有字母和数字两个口袋可以选择，在有很多个口袋的情况下string choose = level == 0 ? let : num;就不好用了，所以我们可以用一个数组把可以选择的口袋放在一起string choosearr[] = {“ABC”, “123”};

#include <iostream>
#include <string>
using namespace std;
string choosearr[] = {"ABC", "123"};
string res ="xx";
void dfs(int level){
    if(level == 2) {
        cout <<"res == "<< res <<endl;
        return;
    }
    string choose = choosearr[level];
    for(char c : choose){
        res[level] = c;
        dfs(level+1);
    }

}
int main(){
    dfs(0);
   return 0;
}

上面写完我们就无限接近了17. 电话号码的字母组合，根据上面的思路我们来完成这一题

17. 电话号码的字母组合

首先来看我们有哪些可以选择的口袋？总共有2 - 9之间的8个口袋可以选择
我们可以选择多少次？ 传入的string digits决定的，也就是digits.size()次

class Solution {
public:
    vector<string> res;
    string choosearr[8] = {"abc", "def", "ghi","jkl","mno","pqrs","tuv","wxyz"};
    int biglevel;
    void dfs(string oneres, int level, string digits){
        if(level == biglevel){
            res.push_back(oneres);
            return;
        }
        string chooose = choosearr[digits[level] - '2'];
        for(char c : chooose){
            oneres[level] = c;
            dfs(oneres, level + 1, digits);
        }
    }
    vector<string> letterCombinations(string digits) {
        biglevel = digits.size();
        if(biglevel == 0) return res;
        string oneres(biglevel,'x');
        // cout<<oneres;
        dfs(oneres, 0, digits);
        return res;
    }
};

排列组合的题目，可以看成每一个袋子里都是“1，2，3”，但是数字不能重复

#include <iostream>
#include <string>
using namespace std;
string choosearr = "123";
bool flag[3];
string res ="xxx";
void dfs(int level){
    if(level == 3) {
        cout <<"res == "<< res <<endl;
        return;
    }
//     for(char c : choosearr){
//         if(c != '|'){
//             res[level] = c;
//             dfs(level+1);
//         }

//     }
     for(int i = 0; i < choosearr.size(); i++){
         char orgin = choosearr[i];
        if(choosearr[i] != '|'){
            res[level] = choosearr[i];
            choosearr[i] = '|';
            dfs(level+1);
             choosearr[i] = orgin;


        }

    }

}
int main(){
    dfs(0);
   return 0;
}