// @Title: 全排列 (Permutations)
// @Author: qisiii
// @Date: 2024-09-19 23:53:21
// @Runtime: 1 ms
// @Memory: 43.5 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), nums);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(list.contains(nums[i])){
                continue;
            }else{
                list.add(nums[i]);
            }
            dfs(result, list, nums);
            list.remove(list.size() - 1);
        }

    }
}

// @Title: 全排列 (Permutations)
// @Author: qisiii
// @Date: 2024-05-10 21:00:12
// @Runtime: 2 ms
// @Memory: 43.8 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> numList = new ArrayList<>();
        for (int i : nums) {
            numList.add(i);
        }
        return permute(numList);
    }

    public List<List<Integer>> permute(List<Integer> nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.size() <= 1) {
            result.add(new ArrayList<>(nums));
            return result;
        }
        for (Integer i : nums) {
            List<Integer> temp = new ArrayList<>(nums);
            temp.remove(i);
            List<List<Integer>> tempList = permute(temp);
            for (List<Integer> tl : tempList) {
                tl.add(0, i);
            }
            result.addAll(tempList);
        }
        return result;
    }
}