字符串的排列

题解方法

• 回溯

回溯

• 通过字符交换，依次固定第 i 位字符。
• 需要排除重复字符，保证在第 i 位上每种字符只出现一次。

1. 遍历交换第 i 位。
2. 递归搜索第 i + 1 位。
3. 恢复交换第 i 位。

核心代码

回溯

private void search(int index) {
	// 搜索至末位，将结果加入 res
	if (index == chars.length - 1) {
		res.add(new String(chars));
		return;
	}
	Set<Character> set = new HashSet<>();
	for (int i = index; i < chars.length; i++) {
		// 当前字符已存在于当前位置，跳过
		if (set.contains(chars[i])) {
			continue;
		}
		set.add(chars[i]);
		swap(index, i);
		search(index + 1);
		swap(index, i);
	}
}

题目来源

字符串的排列 - 力扣（LeetCode）