多个数组的元素全组合

Posted on | Edited on

题目:

给定n个数组，从每个数组中取出一个元素，并进行组合，最终返回所有可能的组合。

递归解法：

简单的dfs即可，当深度到达n时，即把当前字符串添加到最终结果中。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge1(vector<string> & res, string cur, const vector<vector<char> > &arr, int depth)
{
    if( depth == arr.size() )
    {
        res.push_back(cur);
    }
    for( int i = 0 ; i < arr[depth].size() ; i++ )
    {
        cur += arr[depth][i];
        merge1(res, cur, arr, depth+1);
        cur.pop_back();
    }
}

非递归解法

可以用一个队列保存结果信息，每次从队列头取出一个字符串，然后与第i个数组中的每个元素进行组合，然后在压入队列中，注意使用一个#号表示组合完了一个数组。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vector<string> merge2(vector<vector<char> > & arr)
{
    vector<string> res;
    if( arr.size() == 0 )
    {
        return res;
    }
    queue<string> qu;
    for( int i = 0 ; i < arr[0].size() ; i++ )
    {
        string tmp = "";
        tmp += arr[0][i];
        qu.push(tmp);
    }
    qu.push("#");
    for( int i = 1 ; i < arr.size() ; i++ )
    {
        while( qu.front() != "#")
        {
            if( arr[i].size() == 0 )
            {
                qu.push(qu.front());
            }
            else
            {
                for( int j = 0 ; j < arr[i].size() ; j++ )
                {
                    qu.push(qu.front() + arr[i][j]);
                }
            }
            qu.pop();
        }
        qu.pop();
        qu.push("#");
    }
    while( qu.front() != "#")
    {
        res.push_back(qu.front());
        qu.pop();
    }
    return res;
}