题解 | #没有重复项数字的全排列#

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // 结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 当前排列
        ArrayList<Integer> s = new ArrayList<>();
        // 调用回溯方法
        backTrack(res, s, num, 0);
        return res;
    }

    // 定义回溯函数
    public void backTrack(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> s, int[] num, int indexBegin) {
        // 如果当前排列长度等于原数组长度，说明已形成一个完整排列
        if (s.size() == num.length) {
            res.add(new ArrayList<>(s));  // 注意这里需要创建一个新的ArrayList，因为ArrayList是引用类型
            return;
        }
        // 遍历数组中的每个元素
        for (int i = 0; i < num.length; i++) {
            // 如果当前元素已在s中，则跳过
            if (s.contains(num[i])) {
                continue;
            }
            // 添加元素到当前排列
            s.add(num[i]);
            // 递归调用，进行下一层的排列
            backTrack(res, s, num, i);
            // 回溯，移除最后一个元素，尝试下一个可能的元素
            s.remove(s.size() - 1);
        }
    }
}