[LeetCode]Permutations

题目传送门

题目描述：给定一个不含重复元素的整数数组，要求找出该数组中所有可能的排列（即元素顺序的所有不同重排方式），并以列表形式返回这些排列结果，结果的顺序可以任意。

代码：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        Arrays.fill(visited, false);
        List<List<Integer>> result = new ArrayList<>();
        permute(result, nums, visited, 0, new ArrayList<>());
        return result;
    }

    private void permute(List<List<Integer>> result, int[] nums, boolean[] visited, int visitedCount,
                         List<Integer> lastArray) {
        if (visitedCount == nums.length) {
            result.add(new ArrayList<>(lastArray));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                visitedCount += 1;
                lastArray.add(nums[i]);
                permute(result, nums, visited, visitedCount, lastArray);
                lastArray.removeLast();
                visitedCount -= 1;
                visited[i] = false;
            }
        }
    }
}

代码思路：通过一个 visited 数组记录每个元素是否已经被使用，在递归过程中逐步构建当前排列（lastArray）。每一层递归都会遍历所有元素，选择一个尚未使用的元素加入当前路径，并标记为已访问，然后继续递归构建下一个位置；当已选元素数量等于数组长度时，说明形成了一个完整排列，将其加入结果集。递归返回时，通过撤销选择（恢复 visited 状态、移除最后加入的元素、回退计数）实现状态回溯，从而探索所有可能的排列组合。