层级排列组合问题的新思路
本问题探讨了如何通过给定的数组和层级生成一组排列组合。例如，给定数组 a 和 b，两层级的组合可能包括 ab 和 aa。
我们可以采取两种方法来解决这个问题：
方法一：数位替换
我们可以将问题转换成一个数位替换问题。具体步骤如下：
- 首先创建长度为层级的数列，每位可以使用给定数组中的任何字符。
- 对于每一层，我们可以通过将数字增量一位并替换相应的字符来生成新的组合。
- 在替换时，可以通过判断是否能被 11 整除来避免生成全相同的组合（因为对于进位制为 2 的数位系统，全相同的数在进位后仍保持全相同）。
代码示例：
def solve(arr, m, allow_all_same=false): res, cur = [], [''] * m n = len(arr) all_1 = 0 for _ in range(m): all_1 = all_1 * n + 1 for d in range(n ** m): if allow_all_same or d % all_1 != 0: for i in range(m - 1, -1, -1): cur[i] = arr[d % n] d //= n res.append(''.join(cur)) return res
方法二：回溯
我们还可以使用回溯法来生成排列组合。具体步骤如下：
- 每次选取一个数组中的字符添加到已有组合的末尾。
- 然后递归调用函数，在新的组合的基础上继续添加字符。
- 在回溯过程中，我们可以维护一个标志，用于判断已有组合中是否包含重复字符。
代码示例：
def solve(arr, m, allow_all_same=False): res, cur = [], [''] * m def dfs(i, same): if i == m: if not same: res.append(''.join(cur)) return for a in arr: cur[i] = a dfs(i + 1, same and a == cur[i - 1]) for a in arr: cur[0] = a dfs(1, not allow_all_same) return res
