M 46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]
 

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

题目：给定一个包含不同整数的数组nums，返回所有可能的排列。你可以以任何顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

限制条件：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums数组中的所有整数都是唯一的。

该题目是一个经典的排列生成问题，要求给定一个不同整数的数组，生成所有可能的排列。这个问题的一般解决策略是使用一种被称为回溯的技术。在这个问题中，我们尝试在每个位置放置数组中的每个元素，并且通过递归在剩余的位置做同样的操作。为了保证每个排列中的元素都是唯一的，我们需要在递归调用之后将数组恢复到原始状态，这就是所谓的回溯。这个过程可以确保我们遍历了所有可能的排列，因为我们在每个位置尝试了所有可能的元素。


best answer

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

class Solution {
    // 主函数，输入一个整数数组，返回一个列表，该列表中的每个元素都是一个表示排列的列表
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
		permuteUtil(nums, list, 0, nums.length); // 调用辅助函数开始递归
		return list; // 返回排列列表
    }
    // 递归函数，用于生成所有可能的排列
    public  void permuteUtil(int[] nums, List<List<Integer>> list, int left, int right) {
		// 基本情况，如果左边索引等于右边索引，即数组中所有元素都已排列
		if (left == right) {
			List<Integer> arrayList = new ArrayList<>();
			for (int num : nums) { // 将当前排列添加到结果列表中
				arrayList.add(num);
			}
			list.add(arrayList);
			return;
		}
		// 对于数组中的每一个元素，将其作为排列的第一个元素，然后对剩余元素进行递归
		for (int i = left; i < right; i++) {
			swap(nums, left, i); // 将当前元素交换到“首位”
			permuteUtil(nums, list, left + 1, right); // 对剩余的元素进行递归
			swap(nums, left, i); // 回溯，还原数组
		}
	}

	// 辅助函数，用于交换数组中的两个元素
	public  void swap(int[] nums, int left, int right) {
		int temp = nums[left]; // 暂存左边的元素
		nums[left] = nums[right]; // 将右边的元素放到左边
		nums[right] = temp; // 将暂存的左边元素放到右边
	}
}