# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 回溯函数
# words:    单词数组
# ans:      答案数组
# ans_set:  用于判断是否出现重复答案的集合
# path:     当前回溯的路径数组
# used:     判断某元素是否使用过的bool型数组
def dfs(words, ans, ans_set, path, used):
    # 递归终止条件：
    # 路径长度等于单词数组长度，说明所有单词均被使用
    if len(path) == len(words):
        path_str = "".join(path)
        # 若此时路径在此之前没出现过，则加入ans和ans_set中
        if path_str not in ans_set:
            ans.append(path_str)
            ans_set.add(path_str)
        return

    # 横向遍历所有单词
    for i in range(len(words)):
        # 如果单词words[i]已经被使用过，或者和上一个单词相等，则无需再进行回溯，直接跳过
        if used[i] or (i > 0 and words[i] == words[i - 1] and not used[i - 1]):
            continue
        # 状态更新
        used[i] = True
        path.append(words[i])
        # 回溯
        dfs(words, ans, ans_set, path, used)
        # 回滚
        used[i] = False
        path.pop()


# 输入数组长度，单词数组
n = int(input())
words = input().split()

# 对words进行从小到大排列
# 这样才能保证组合出来每一个密码都是按升序排序
words.sort()

ans = list()
used = [False] * n
# 递归调用入口
dfs(words, ans, set(), [], used)
# 逐行输出答案，必须对答案列表进行排序
ans.sort()
for res in ans:
    print(res)

Java

import java.util.*;

public class Main {
    public static void dfs(String[] words, List<String> ans, Set<String> ansSet, List<String> path, boolean[] used) {
        if (path.size() == words.length) {
            String pathStr = String.join("", path);
            if (!ansSet.contains(pathStr)) {
                ans.add(pathStr);
                ansSet.add(pathStr);
            }
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (used[i] || (i > 0 && words[i].equals(words[i - 1]) && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(words[i]);
            dfs(words, ans, ansSet, path, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline
        String[] words = scanner.nextLine().split(" ");

        List<String> ans = new ArrayList<>();
        boolean[] used = new boolean[n];
        dfs(words, ans, new HashSet<>(), new ArrayList<>(), used);

        Collections.sort(ans);
        for (String res : ans) {
            System.out.println(res);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void dfs(const vector<string>& words, vector<string>& ans, set<string>& ansSet, vector<string>& path, vector<bool>& used);

int main() {
    int n;
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }

    vector<string> ans;
    set<string> ansSet;
    vector<bool> used(n, false);
    vector<string> path;

    dfs(words, ans, ansSet, path, used);

    sort(ans.begin(), ans.end());
    for (const string& res : ans) {
        cout << res << endl;
    }

    return 0;
}

void dfs(const vector<string>& words, vector<string>& ans, set<string>& ansSet, vector<string>& path, vector<bool>& used) {
    if (path.size() == words.size()) {
        string pathStr;
        for (const string& str : path) {
            pathStr += str;
        }
        if (ansSet.find(pathStr) == ansSet.end()) {
            ans.push_back(pathStr);
            ansSet.insert(pathStr);
        }
        return;
    }

    for (int i = 0; i < words.size(); i++) {
        if (used[i] || (i > 0 && words[i] == words[i - 1] && !used[i - 1])) {
            continue;
        }
        used[i] = true;
        path.push_back(words[i]);
        dfs(words, ans, ansSet, path, used);
        used[i] = false;
        path.pop_back();
    }
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const inputLines = [];
rl.on('line', (line) => {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        solve();
        rl.close();
    }
});

function solve() {
    const n = parseInt(inputLines[0]);
    const words = inputLines[1].split(" ");

    // 上条路径 path，ans用于结果组
    const ans = [];
    const ansSet = new Set();
    const used = new Array(n).fill(false);

    // 通用转换成 dfs 实现
    function dfs(path) {
        if (path.length === words.length) {
            const pathStr = path.join("");
            if (!ansSet.has(pathStr)) {
                ans.push(pathStr);
                ansSet.add(pathStr);
            }
            return;
        }

        for (let i = 0; i < words.length; i++) {
            if (used[i] || (i > 0 && words[i] === words[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.push(words[i]);
            dfs(path);
            path.pop();
            used[i] = false;
        }
    }

    words.sort(); // 排序以处理重复元素
    dfs([]);

    ans.sort();
    for (let res of ans) {
        console.log(res);
    }
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strings"
)

var (
        ans    []string        // 存储最终结果
        ansSet map[string]bool // 去重集合
        used   []bool          // 标记是否使用
)

func dfs(words []string, path []string) {
        if len(path) == len(words) {
                pathStr := strings.Join(path, "")
                if !ansSet[pathStr] {
                        ans = append(ans, pathStr)
                        ansSet[pathStr] = true
                }
                return
        }

        for i := 0; i < len(words); i++ {
                if used[i] || (i > 0 && words[i] == words[i-1] && !used[i-1]) {
                        continue
                }
                used[i] = true
                path = append(path, words[i])
                dfs(words, path)
                path = path[:len(path)-1]
                used[i] = false
        }
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        var n int
        fmt.Fscanln(reader, &n)

        line, _ := reader.ReadString('\n')
        words := strings.Fields(strings.TrimSpace(line))

        sort.Strings(words) // 排序，确保处理重复元素时顺序正确

        used = make([]bool, n)
        ansSet = make(map[string]bool)
        dfs(words, []string{})

        sort.Strings(ans)
        for _, s := range ans {
                fmt.Println(s)
        }
}

时空复杂度

时间复杂度：O(N*N!)。

空间复杂度：O(N)。