【算法题】47. 全排列 II

这篇具有很好参考价值的文章主要介绍了【算法题】47. 全排列 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2:

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

提示:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

题解

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

来自力扣官方题解文章来源地址https://www.toymoban.com/news/detail-790587.html

到了这里,关于【算法题】47. 全排列 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(42)
  • Day 29 | 回溯 491.递增子序列 、 46.全排列 、47.全排列 II

    题目 文章讲解 视频讲解 思路:去重原则:元素,树层不可以重复取,树枝可以。hash这种去重方式不需要回溯 题目 文章讲解 视频讲解 思路:used[i]这种去重方式需要回溯 注意比较两种去重方式 permute(排列) 题目 文章讲解 视频讲解 思路:去重之前一定做排序,used[i-1] =

    2024年01月25日
    浏览(44)
  • 【算法与数据结构】518、LeetCode零钱兑换 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题的硬币是无数的,因此本题可以抽象成一个完全背包问题。完全背包和01背包的不同之处在于完全背包式从前往后遍历的。在本题的完全背包问题中,amount代表背包的最大重量

    2024年01月23日
    浏览(43)
  • 【算法与数据结构】63、LeetCode不同路径 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :参考【算法与数据结构】62、LeetCode不同路径的题目,可以发现本题仅仅是多了障碍物。我们还是用动态规划来做。有障碍物的地方无法到达,因此路径数量为0,只需要将障碍物位

    2024年02月02日
    浏览(53)
  • 【算法与数据结构】1049、LeetCode 最后一块石头的重量 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题需要得到石头之间两两粉碎之后的最小值,那么一个简单的思路就是将这堆石头划分成大小相近的两小堆石头,然后粉碎,这样得到的结果必然是最优值。那么如何划分呢?我

    2024年01月21日
    浏览(45)
  • Day31 46全排列 47全排列II 回溯去重tips 51N皇后 37解数独

    给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]  排列问题与组合问题的不同之处就在于,没有startIndex,同时需要设置一个used数组,遍历过的就设置成true,下次遇到时跳过。 给定一个可包含重

    2024年01月20日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(57)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(50)
  • 代码随想录刷题笔记 DAY 29 | 非递减子序列 No.491 | 全排列 No.46 | 全排列 II No. 47

    01. 非递减子序列(No. 491) 题目链接 代码随想录题解 1.1 题目 给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种

    2024年02月21日
    浏览(42)
  • 【数据结构】 算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月14日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包