某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。

返回结果 无顺序要求，但不能含有重复的元素。

示例 1：

**输入：**goods = “agew”
输出：[“aegw”,“aewg”,“agew”,“agwe”,“aweg”,“awge”,“eagw”,“eawg”,“egaw”,“egwa”,“ewag”,“ewga”,“gaew”,“gawe”,“geaw”,“gewa”,“gwae”,“gwea”,“waeg”,“wage”,“weag”,“wega”,“wgae”,“wgea”]

提示：

1 <= goods.length <= 8

全排列问题，首先想到递归，但是题目中没有说goods中元素部重复。

所以直接全排列会产生很多重复，我们可以在最后去重，也可以在全排列过程中去重。

对于 aab，直接全排列其实就是我们把aa看成了a1 a2去排列，我们需要保证a1出现过的位置不再列举a2。

有一种方法就是固定a1 a2出现的顺序，保证列举a时只有列举a1之后再列举a2。

假设当前列举goods[i]，首先判断goods[i]是否已经被使用（去重前也需要），然后判断goods[i-1]与goods[i]是否相等，相等的话还需要判断goods[i-1]是否已经被列举（a1被列举后才能使用a2）。

为了方便列举我们可以先对goods进行排序，让相同元素相邻

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
class Solution {
public:
    vector<string> ans;
    vector<bool> flag = vector<bool>(20);
    vector<string> goodsOrder(string goods) {
        sort(goods.begin(), goods.end());
        string mid;
        f(mid, 0, goods.size(), goods, flag);
        return ans;
    }
    void f(string mid, int now, int len, string &goods, vector<bool> &flag) {
        if (now == len) {
            ans.push_back(mid);
            return;
        }
        for (int j = 0; j < len; j++) {
            if (flag[j] || (j > 0 && flag[j - 1] && goods[j - 1] == goods[j]))
                continue;
            string mm = mid + goods[j];
            flag[j] = true;
            f(mm, now + 1, len, goods, flag);
            flag[j] = false;
        }
    }
};