[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

시간 복잡도) O(n * n2)

공간 복잡도) O(n)

 

class Solution
{
public:
	int ans = 0;

	bool isUnique(string s)
	{
		set<char> st(s.begin(), s.end());
		return (st.size() == s.length());
	}

	// 백트래킹
	void solve(vector<string>& arr, int index = 0, string s = "")
	{
		if (!isUnique(s))
			return;
		
		ans = max(ans, (int)s.length());
		
		for (int i = index; i < arr.size(); i++)
			solve(arr, i + 1, s + arr[i]);
	}

	int maxLength(vector<string>& arr)
	{
		solve(arr);
		return ans;
	}
};