LeetCode全排列、全排列II

【问题描述】 给定一个 没有重复 数字的序列，返回其所有可能的全排列。

【示例】

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

class Solution {
          
   
    public void dfs(int m,int []a,boolean vis[],List<Integer> sub,List<List<Integer>> ans) {
          
   
		if(m==a.length) {
          
   
			//sub记录一个排列方案
            /*在 Java 中，参数传递是值传递，对象类型变量在传参的过程中，
            复制的是变量的地址。这些地址被添加到 ans 变量，但                
            实际上指向的是同一块内存地址，因此我们会看到6个空的列表对象。
            */

			ans.add(new ArrayList<>(sub));
			return;
		}
		for(int i=0;i<a.length;i++) {
          
   
			if(!vis[i]) {
          
   
				vis[i]=true;
                sub.add(a[i]);
				dfs(m+1,a,vis,sub,ans);
				sub.remove(sub.size()-1);
                vis[i]=false;
				
			}
		}
		
	}
    public List<List<Integer>> permute(int[] nums) {
          
   
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        List<Integer> sub=new ArrayList<>();
        boolean [] vis=new boolean[nums.length];
        dfs(0,nums,vis,sub,ans);
        return ans;

    }
}

【题目描述】 给定一个可包含重复数字的序列，返回所有不重复的全排列。

【示例】

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

import java.util.Arrays;
class Solution {
          
   
    public List<List<Integer>> permuteUnique(int[] nums) {
          
   
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        List<Integer> sub=new ArrayList<>();
        boolean [] vis=new boolean[nums.length];
        //要先排序 使得相同元素紧挨在一起
        Arrays.sort(nums);
        dfs(0,nums,vis,sub,ans);
        return ans;

    }
    public void dfs(int m,int []a,boolean vis[],List<Integer> sub,List<List<Integer>> ans) {
          
   
		if(m==a.length) {
          
   
			ans.add(new ArrayList<>(sub));
			return;
		}
		for(int i=0;i<a.length;i++) {
          
   
			if(!vis[i]) {
          
   
                if(i>0&&a[i-1]==a[i]&&!vis[i-1]) continue;
				vis[i]=true;
                sub.add(a[i]);
				dfs(m+1,a,vis,sub,ans);
				sub.remove(sub.size()-1);
                vis[i]=false;
				
			}
		}
		
	}

}