子集与全排列问题(力扣78,90,46,47)

系列文章目录

子集和全排列问题与下面的组合都是属于回溯方法里的,相信结合前两期,再看这篇笔记,更有助于大家对本系列的理解

一、组合回溯问题
二、组合总和问题



题目

Problem: 78. 子集
Problem: 90. 子集 II
Problem: 46. 全排列
Problem: 47. 全排列 II

子集II与全排列II都只是在前面的基础上加了题目所给的nums数组里的元素可重复这个条件
子集问题
给你一个整数数组 nums ,数组中的元素互不相同 。返回该数组所有可能的
子集(幂集)。解集 不能包含重复的子集。你可以按任意顺序返回解集。

示例 1:

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

示例 2:

输入:nums = [0]
输出:[[],[0]]

全排列问题
给定一个不含重复数字的数组 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]]


子集

一、思路

与组合和组合总和问题不同的是每遍历到一个树的结点,都要把结果加入到result结果集里面,而不是到叶子结点时,才收集结果

例:从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合
在这里插入图片描述

二、解题方法

回溯三部曲

  1. 递归函数的返回值以及参数:
    参数为startIndex和nums整数数组
 public void backTracking(int[] nums,int startIndex)
  1. 回溯函数终止条件:
    到叶子结点时就退出递归,去遍历其它路径上的结果
if(startIndex >= nums.length) {
            return;
        }
  1. 单层搜索的过程:
    每遍历一次都把元素添加到路径path中,递归回溯,每次递归startIndex都从后一位递归,否则会造成重复的组合。
for(int i = startIndex;i<nums.length;i++) {
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.removeLast();
        }

在每层递归函数里,都要把当前路径添加到result结果集中,要写在终止条件之前,否则退出之后,当前结果还没有保存就回溯其它路径上的结果了。

result.add(new ArrayList<>(path));

优化:在这里其实可以省略掉终止条件,因为就算遍历超过叶子结点了,不满足for循环的条件里,for循环里面也不会执行,就直接return了。

三、Code

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums,0);
        return result;
    }

    public void backTracking(int[] nums,int startIndex) {
        result.add(new ArrayList<>(path));
        if(startIndex >= nums.length) {
            return;
        }
        for(int i = startIndex;i<nums.length;i++) {
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.removeLast();
        }
    }
}

子集II

一、思路

这道题与子集I的区别在于题目给的数组元素可重复,这就要对组合结果去重,与组合总和II是相同的套路,都是先排序之后,再判断前面同一层是否出现了相同的访问过的元素,如果出现了则直接跳过这次循环

在这里插入图片描述

二、解题方法

与上面的子集问题I多了先对nums数组进行排序,在for循环内对横向遍历去重,去重的方法和组合总和II是一样的有以下两种:

  • used数组:
    如果前面的元素和当前元素相同,并且i>0,前面的元素没有使用过,说明不是同一条路径下使用过的的元素,而是同一层内的
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
  • startIndex:
    如果前面的元素和当前元素相同,并且startIndex已经不是第一个开始遍历的,则直接跳过这次循环
if(i > startIndex && nums[i] == nums[i-1]){
                continue;
            }

三、Code

used数组

class Solution {
   List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
   LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
   boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }
    
    private void subsetsWithDupHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));

        if (startIndex >= nums.length){
            return;
        }

        for (int i = startIndex; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

startIndex

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums,0);
        return result;
    }

    public void backTracking(int[] nums,int startIndex) {
        result.add(new ArrayList<>(path));

        if(startIndex >= nums.length) {
            return;
        }

        for(int i = startIndex;i<nums.length;i++) {
            if(i > startIndex && nums[i] == nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums,i + 1);
            path.removeLast();
        }
    }
}

全排列

一、思路

全排列的话[1,2]和[2,1]是不一样的排列,与组合不同,排列要求顺序,所以不需要使用startIndex,只需判断元素是否使用过,如果不判断同一条路径path上的结果是否使用过的话,会一直重复遍历同一个元素,例如:整数数组为[1,2,3,4],那么就会一直遍历1,有两种判断的办法:
一是used数组,二是path.contains(nums[i])

二、解题方法

used数组
在这里插入图片描述

  1. 递归函数的返回值以及参数:
    参数为nums整数数组,创建一个used布尔类型的数组,长度为nums数组的长度
private void permuteHelper(int[] nums)
  1. 回溯函数终止条件:
    到达叶子结点时,就把结果添加到结果集里,退出递归
if (path.size() == nums.length){
    result.add(new ArrayList<>(path));
    return;
}
  1. 单层搜索的过程:
    for循环从第一个元素开始遍历,used数组判断如果为true,则跳过这次循环,找数组里下一个元素,没有使用过的话,就把元素添加到path里,并让used数组为true,递归调用,回溯撤销元素,让used数组为false
for (int i = 0; i < nums.length; i++){
            if (used[i]){//使用过该元素
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }

path.contains(nums[i]):
只要把for循环内的判断used数组改为path.contains(nums[i])即可,判断path有没有添加过该元素

if(path.contains(nums[i])){
    continue;
}

三、Code

used数组

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (used[i]){//使用过该元素
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

path.contains(nums[i])

class Solution {
    List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        backTracking(nums);
        return result;
    }

    public void backTracking (int[] nums) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0;i<nums.length;i++) {
            if(path.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
        }
    }
}

全排列II

一、思路

此题比上面的 全排列I 只多了一个数组元素可重复,与组合总和II、子集II是相同的都要进行先排序再去重,用到used数组判断同一层是否使用过,使用过的话,直接跳过这次循环
在这里插入图片描述

二、解题方法

与全排列I使用used数组的回溯三部曲大致相同,仅仅多了先对数组进行排序,随后判断同一层是否使用过,这个与组合总和II,子集II的通过used数组判断去重是一样的,在此省略

三、Code

class Solution {
    List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    private void backTracking(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            // 同一层用过直接跳过去重
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }

            // 同一条结果路径上没有使用过
            if (used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                path.removeLast();
                used[i] = false;
            }
            
        }
    }
}

总结

以上就是针对这道题的刷题笔记,通过这三篇博客,我们可以看到回溯算法在解决组合、排列等问题时的应用。其基本思想是通过递归和回溯来探索所有可能的解空间,并及时剪枝以避免重复计算,从而高效地求解问题。可以总结出如下回溯的套路:

去重:先对数组进行排序再判断同一层是否使用过相同元素if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){ continue; }

排列和组合都是在叶子结点收集结果集,而子集则是在树的每一个结点都要进行收集结果集

希望本文对你理解和解决组合总和问题有所帮助!🌹

相关推荐

  1. 46. 排列

    2024-04-03 10:04:01       17 阅读
  2. :78. 子集

    2024-04-03 10:04:01       19 阅读
  3. :47. 排列 II

    2024-04-03 10:04:01       19 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 10:04:01       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 10:04:01       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 10:04:01       9 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 10:04:01       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 10:04:01       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 10:04:01       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 10:04:01       10 阅读

热门阅读

  1. ARP地址解析协议 详解

    2024-04-03 10:04:01       4 阅读
  2. Redis实战

    2024-04-03 10:04:01       4 阅读
  3. Pathlib库的有哪些神奇功能在Python中

    2024-04-03 10:04:01       4 阅读
  4. 速盾:cdn加速https额外收费吗?

    2024-04-03 10:04:01       5 阅读
  5. pytorch | yolov5 Can not get arrribute SiLU

    2024-04-03 10:04:01       5 阅读
  6. 常见哈希算法及其应用场景

    2024-04-03 10:04:01       4 阅读
  7. 设计模式(14):命令模式

    2024-04-03 10:04:01       3 阅读
  8. 1344: 【递推】【入门】流感传染

    2024-04-03 10:04:01       4 阅读
  9. WebKit内核架构深度解析:核心技术与工作机制

    2024-04-03 10:04:01       5 阅读
  10. web有哪些方式可以实时更新数据

    2024-04-03 10:04:01       6 阅读
  11. vue 基础回顾

    2024-04-03 10:04:01       3 阅读
  12. 【2024最新】vue3的基本使用(超详细)

    2024-04-03 10:04:01       5 阅读
  13. freertosday3

    2024-04-03 10:04:01       3 阅读