// 暴力搜索
class Solution {
public:
    vector<string> result;
    string str;
    vector<int> flag;  // 记录已经使用过的字符
    vector<string> permutation(string s) {
        // 判断边界条件
        if(s == "")
            return result;

        // 是相同的元素在一起
        sort(s.begin(), s.end());

        // 初始化标记数组
        flag.resize(s.size(), 1);

        // 暴力搜索
        dfs(s, 0, s.size());

        // 返回所有结果集
        return result;
    }

    void dfs(string s, int start, int len)
    {
        // 当前搜索的长度已经满足要求
        if(start == len)
        {
            result.push_back(str);
            return;
        }

        for(int i = 0; i < len; ++i)
        {
            // 前一个相同的元素没有使用时，当前元素不能先使用
            // 等下一轮递归进行的时候从头遍历开始进行使用
            if(i && s[i] == s[i - 1] && flag[i - 1] == 1)
            {
                continue;
            }

            if(flag[i] == 1)
            {
                str += s[i];
                flag[i] = 0;
                dfs(s, start + 1, len);

                // 恢复原有状态
                flag[i] = 1;
                str.pop_back();
            }
        }

        return ;
    }
};