[数据结构与算法]【leetcode】没有重复元素集合的全排列

一、题目描述

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

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

二、代码思路

首先，我们直接能想到这是一个经典的回溯问题，也就是说针对每个元素逐步的判断，判断是否选取，从而形成整个的搜索树。回溯的思想已经很明确，如何实现？

最原始的回溯算法：

最原始的回溯，其实就是79题，所有子集：

public void dfs(int cur, int [] nums) {
        //表示此时把整个nums数组各个元素都判断了一下
        //就是指每个元素都判断了一边是否能够加入，并得出了一种结果。
        //对应到二叉树上就是一条从根节点到叶子节点的一条路径
        //对应的一种选择结果
        //当然，树中的每条路径都对应一种选择结果，有很多选择结果。
        if (cur == nums.length) {
            ans.add(new ArrayList(t));
            return;
        }
        //假设该元素可以被选
        t.add(nums[cur]);
        //接着判断下一个元素
        dfs(cur + 1, nums);
        //该元素如果不选
        t.remove(t.size() - 1);
        //判断该元素未被选的情况
        dfs(cur + 1,nums);
    }

也可以理解为二叉搜索树回溯算法，表现形式就是一颗二叉完全搜索树（不含剪纸操作）。

显然这种写法，是有劣势和优势的。

优势劣势如下表：

多叉搜索树：

private void dfs(int[] nums, int cur) {
        if (cur == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            sum += 1;
            list.add(nums[i]);
            dfs(nums, cur + 1);
            sum -= 1;
            list.remove(list.size() - 1);
        }
    }

多叉搜索树 + 判断：

private void dfs(int[] nums, int cur) {
        if (sum == nums.length) {
            res.add(new LinkedList(list));
            return;
        }
        if (cur == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
        	//判断该元素是不是能选
        	//和多叉搜索树结合起来很好用
        	//可以解决全排列问题
            if (flags[i] != 0) {
                continue;
            }
            flags[i] = 1;
            sum += 1;
            list.add(nums[i]);
            dfs(nums, cur + 1);
            sum -= 1;
            list.remove(list.size() - 1);
            flags[i] = 0;
        }
    }

三、代码题解

分为三个版本的题解，每个版本进行逐步优化

3.1 多叉树 + set去重

package leetcode.lc20221020;

import java.util.*;

/*
 * @author lzy
 * @version 1.0
 * @Desc 多叉选择树 + 全排列 + 数组中没有重复元素 + 不可重复选择元素（使用多叉树for循环判断时可以使用Set判断是否已经选中该元素，从而实现不可重复选择元素） + set去重
 * 效率不是很高，所以有了solution2，使用填空法
 * */
public class Solution01 {
    private int sum;
    private List<Integer> list = new LinkedList();
    private List<List<Integer>> res = new ArrayList();
    private Set<Integer> set = new HashSet();
    public List<List<Integer>> permute(int[] nums) {
        //这不就是回溯吗
        dfs(nums, 0);
        return res;
    }
    private void dfs(int[] nums, int cur) {
        if (sum == nums.length) {
            res.add(new LinkedList(list));
            return;
        }
        if (cur == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                continue;
            }
            sum += 1;
            set.add(nums[i]);
            list.add(nums[i]);
            dfs(nums, cur + 1);
            sum -= 1;
            list.remove(list.size() - 1);
            set.remove(nums[i]);
        }
    }
}

3.2 多叉树 + 数组去重（空间复杂度较高）

private void dfs(int[] nums, int cur) {
        if (sum == nums.length) {
            res.add(new LinkedList(list));
            return;
        }
        if (cur == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (flags[i] != 0) {
                continue;
            }
            flags[i] = 1;
            sum += 1;
            list.add(nums[i]);
            dfs(nums, cur + 1);
            sum -= 1;
            list.remove(list.size() - 1);
            flags[i] = 0;
        }
    }

3.3 多叉树 + 选择 + 位运算去重（空间复杂度较低）

private void dfs(int[] nums, int cur) {
        if (sum == nums.length) {
            res.add(new LinkedList(list));
            return;
        }
        if (cur == nums.length) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int temp = 1 << nums[i] + 10;
            //判断特定位置是否为1
            if ((flag & temp) != 0) {
                continue;
            }
            sum += 1;
            list.add(nums[i]);
            //将特定位置置为1
            flag = flag | temp;
            dfs(nums, cur + 1);
            sum -= 1;
            list.remove(list.size() - 1);
            //将特定位置再置为0
            flag = flag & (~temp);
        }
    }