Java解决传递信息

Java解决传递信息

01 题目

• 给定一个不含重复数字的数组 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 中的所有整数 互不相同

02 知识点

• 递归
• 动态规划

03 我的题解思路

public class permute {
	public static void main(String[] args) {
//		测试数据
		int[] nums= {1,1,2};
		List<List<Integer>> list=permute(nums);
		for (List<Integer> list2 : list) {
			for (Integer integer : list2) {
				System.out.print(integer+" ");
			}
			System.out.println();
		}
	}
	public static List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> rs=new ArrayList<>();//返回值，记录了所有排列
		List<Integer> in=new ArrayList<>();//记录每一种排序
		for (Integer integer : nums) {
			in.add(integer);//循环整个数组，将值填入集合
		}
		//记录排列长度
		int n=nums.length;
//		从0开始递归，递归参数分别是当层排序，总排列，当前层数，总层数
		backtracking(in, rs, 0, n);
		return rs;
    }
	public static void backtracking(List<Integer> in,List<List<Integer>> rs,int level,int n) {
		if(level==n) {//当前层数等于总层数时，递归终止
			rs.add(new ArrayList<>(in));
			return;
		}
//		从当前层数开始循环，递归次数为（总层数-当前层数+1）
		for (int i = level; i < n; i++) {
//			利用Collections的封装方法，交换索引为level和i的in列表
			Collections.swap(in, level, i);
//			接着往下递归
			backtracking(in, rs, level+1, n);
//			当前递归结束后换回来
			Collections.swap(in, level, i);
		}
	}
}