# Leetcode [No. 1239] Maximum Length of a Concatenated String with Unique Characters (MEDIUM)

+ 2024/01/23 Daily Challenge

## 題目

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/?envType=daily-question&envId=2024-01-23

## 思路
+ 這個解法其實是GPT先幫我生組合的code我才接下來開始做的，組合真的很好難喔QAQQ
+ 首先我把所有合法的組合窮舉出來後，把所有字串加起來，就是答案ㄌ

class Solution {
public:
    int maxLength(vector<string>& arr) {
        int ans = 0;
        vector<string> currentCombination;
        generateCombinations(arr, currentCombination, 0, arr.size(), ans);
        return ans;
    }
    void generateCombinations(const std::vector<string>& arr, std::vector<string>& currentCombination, int start, int size, int& maxLength) 
    {
        // 输出当前组合
        if (!currentCombination.empty()) 
        {
            int sum = 0 ;
            for (string i : currentCombination) 
            {
                sum += i.size();
            }
            maxLength = max(maxLength, sum);
        }

        // 递归生成所有可能的组合
        for (int i = start; i < size; ++i) 
        {
            // 添加当前元素到组合中
            currentCombination.push_back(arr[i]);
            if(isLegal(currentCombination))
            {
                // 递归调用生成以当前元素为开头的组合
                generateCombinations(arr, currentCombination, i + 1, size, maxLength);
            }
            // 移除当前元素，进行下一个组合的生成
            currentCombination.pop_back();
        }
    }

    bool isLegal(vector<string>& currentCombination)
    {
        unordered_set<char> s;
        for(int i = 0 ; i < currentCombination.size(); i++)
        {
            for(int j = 0 ; j < currentCombination[i].size(); j++)
            {
                if(s.count(currentCombination[i][j]) != 0)
                {
                    return false;
                }
                else
                {
                    s.insert(currentCombination[i][j]);
                }
            }
        }
        return true;
    }
};

### 解法分析

+ time complexity: O(2^n)