题解 | #字符串的排列#

遇到排列组合问题，一般使用回溯法求解。

回溯法模板：

result = {}
 void backtrack(路径, 选择列表):
    if (满足结束条件){
        result.add(路径)
        return
    }
    for (选择 in 选择列表){
        做选择
        backtrack(路径, 选择列表)
        撤销选择
    }

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        HashSet<String> ans = new HashSet<>();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        backtrack(list,0,str.length(), ans);
        return new ArrayList<>(ans);
    }

    public void backtrack(List<Character> list, int start, int end, HashSet<String> ans) {
        if (start == end) {
            // 收集结果
            String str = "";
            for (int i = 0; i < list.size(); i++) {
                str += list.get(i);
            }
            ans.add(str);
        }
        for (int i = start; i < end; i++) {
            Collections.swap(list, i, start);
            backtrack(list, start + 1, end, ans);
            Collections.swap(list, i, start);
        }
    }
}