我的知识海洋

What are you following

  • 首页
  • 标签
  • 分类目录
  • 文章归档
  • 行路万里
  • 读书万卷
  • About Me

  • 搜索
面经 解决方案 操作系统 Java源码 开源 GSoC 哲学 中间件 回溯 链表 书 top 数据库 分布式 滑动窗口 配置 动态规划 前缀树 并查集 Redis 总结 年终总结 面试 算法基础

【随想录9 】回溯及模版(子集、排列问题)

发表于 2022-01-10 | 分类于 学习 | 阅读次数 808
# 算法基础 # 回溯
【Sharding-JDBC-3】分库分表策略及常见分片算法
活出生命的意义

模版

// 结果集合
		public List<List<Integer>> res = new ArrayList<>();
// 路径集合
    public LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> model(int[] nums) {
      // 根据是否需要指定开始位置进行传参
        backtracking(nums,0);
        return res;
    }
    public void backtracking(int []nums,int index){
      // 根据结果叶子节点还是节点进行结果收集
        res.add(new ArrayList<>(path));
        //根据 是否需要依赖上一位置进行遍历
        for(int i=index;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }

分类

(1) 元素无重复不可复选

即 nums 中的元素都是唯一的,每个元素最多只能被使用一次

子集(元素无重不可复选)

78. 子集

输入一个无重复元素的数组 nums,其中每个元素最多使用一次,请你返回 nums 的所有子集。

组合(元素无重不可复选)

77. 组合

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

大小为 k 的组合就是大小为 k 的子集

排列(元素无重不可复选)

46. 全排列

给定一个不含重复数字的数组 nums,返回其所有可能的全排列


(2) 元素可重复不可复选

即 nums 中的元素可以存在重复,每个元素最多只能被使用一次

子集/组合(元素可重不可复选)

90. 子集 II

给你一个整数数组 nums,其中可能包含重复元素,请你返回该数组所有可能的子集

排列(元素可重不可复选)

47. 全排列 II


(3) 元素无重可复选

即 nums 中的元素都是唯一的,每个元素可以被使用若干次

子集/组合 (元素无重可复选)

39. 组合总和

排列(元素无重可复选)

1. 待选元素互不相同,且不可重复选择

1.1 子集(元素无重不可复选)

78. 子集

q1

数组元素互不相同,所以不需要考虑去重的问题

==子集==收集的结果应该是递归树中的==每一个节点==,所以在进入回溯函数之后就直接收集结果

    public List<List<Integer>> res = new ArrayList<>();
    public LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return res;
    }
    public void show(int []nums,int index){
        res.add(new ArrayList<>(path));
     
        for(int i=index;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }	

1.2 组合(元素无重不可复选)

77. 组合

image-20220915195317552

相当于是子集问题

给你输入一个数组 nums = [1,2..,n] 和一个正整数 k,请你生成所有大小为 k 的子集

==相当于收集第k层的节点==

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

    public List<List<Integer>> combine(int n, int k) {
        back(n,k,1);
        return res;
    }
    public void back(int n,int k,int index){
      // 收集第 k 层上的节点
        if(path.size()==k){
            res.add(new ArrayList<>(path));
        }
        for(int i=index;i<=n;i++){
            path.add(i);
            back(n,k,i+1);
            path.removeLast();
        }
    }
}

1.3 排列(元素无重不可复选)

46. 全排列

tt

收集所有叶节点的结果集合

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;
        backtrack(nums, path);
        return result;
    }
    public void backtrack(int[] nums, LinkedList<Integer> path) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
        }
        for (int i =0; i < nums.length; i++) {
            // 如果path中已有,则跳过
            if (path.contains(nums[i])) {
                continue;
            } 
            path.add(nums[i]);
            backtrack(nums, path);
            path.removeLast();
        }
    }
}

2. 元素可重复不可复选

2.1 子集(元素可重不可复选)

90. 子集 II

q2

可能包含重复元素,需要进行去重处理

借助卡哥的图翻译翻译:

tt

可以使用一个标记数组来判断待选集合中每个元素是否被使用过,

以【1,2,2】 为例子

最左边的遍历会产生【】、【1】、【1,2】、【1,2,2】 这四个集合

在【1,2,2】 产生之后会往上回溯,先回溯到集合为【1,2】,因为没有新的元素可以使用,再回溯到集合中只有【1】

此时第一个2已经使用过,而唯一可以选的元素的值也是2,需要跳过

对应下面代码中的

 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]==true)
    continue;        

它的意思是,如果当前待选元素与前一个元素相等,且前一个元素已经使用过了,那么这条分支就不应该继续往下走,因为前面已经走过了,所以continue,继续当前位置的 的 下一个元素的选择。

代码:

class Solution {
   List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
   LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
   boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            result.add(path);
            return result;
        }
        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]==true){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

优化:

如果当前选择的元素大于了开始选择的位置

且这个数字和它前面的数字一样,那就跳过

因为在选择这个元素之前,一定选择过了之前的和它相等的元素,(i>start)

if(i>start && nums[i-1]==nums[i])continue;

完整代码:

    List<List<Integer>>  res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
      Arrays.sort(nums);
      subsetsWithDupHelper(nums,0);
      return res;
    }

    private void subsetsWithDupHelper( int[] nums, int start ) {
      res.add( new ArrayList<>(path) );

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

2.2 组合问题(元素可重不可复选)

40. 组合总和 II

image-20220915200054133

换个问法就变成子集问题了:请你计算 candidates 中所有和为 target 的子集。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        back(candidates,target,0,0);
        return res;
    }
    private void back(int[] candidates,int target,int index,int sum){
        if(sum==target){
            res.add(new ArrayList<>(path));
        }
        for(int i=index;i<candidates.length;i++){
            if(sum+candidates[i]>target  ){
                return;
            }
            if( i>index && candidates[i]==candidates[i-1] ){
                continue ;
            }
            sum+=candidates[i];
            path.add(candidates[i]);
            back(candidates,target,i+1,sum);
            path.removeLast();
            sum-=candidates[i];
        }
    }
}

2.3 排列(元素可重不可负复选)

47. 全排列 II

q5

因为包含了重复元素,需要去重

【2,1(a),1(b)】或【2,1(b),1(a)】只能出现一个

交换律告诉我们,对于全排列,只要数组的元素一样,那么最后的全排列结果集合一定是一样的

为了方便判断元素是否使用过,所以先对数组排序。

和之前的去重一样,在同一层上,只允许相同值的元素使用一次

 if ( i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false ) 
    continue;            

    //结果集合
    List<List<Integer>> res = new ArrayList<>();
    //路径集合
    LinkedList<Integer> path = new LinkedList<>();


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


    private void getPermute( int[] nums, boolean[] used, int start ) {
        if ( path.size() == nums.length ) {
            res.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] );
                getPermute( nums, used, i + 1 );
                path.removeLast();
                used[i] = false;
            }
        }
    }
}

这里不能直接使用 i>start的去重是因为之前是组合问题,需要从下一个元素开始,但全排列是要求所有元素都使用到。

3. 元素无重可复选

3.1 子集/组合(元素无重可复选)

39. 组合总和

image-20220915200618034

说是组合问题,实际上也是子集问题:candidates 的哪些子集的和为 target?

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        back(candidates,target,0,0);
        
        return res;
    }
    private void back(int[]candidates,int target,int index,int sum){
        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum>target)return;
        // 从index 开始,不会往前找
        for(int i=index;i<candidates.length;i++){
            if(sum+candidates[i]>target)continue;

            sum+=candidates[i];
            path.add(candidates[i]);
            back(candidates,target,i,sum);
            path.removeLast();
            sum-=candidates[i];
        }
    }
}

3.2 排列(元素无重可复选)

nums 数组中的元素无重复且可复选的情况下,有哪些排列?

输入 nums = [1,2,3],那么这种条件下的全排列共有 3^3 = 27 种:

[
  [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
  [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
  [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]

直接无需去重

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();

public List<List<Integer>> permuteRepeat(int[] nums) {
    backtrack(nums);
    return res;
}
// 回溯算法核心函数
void backtrack(int[] nums) {
    // base case,到达叶子节点
    if (track.size() == nums.length) {
        // 收集叶子节点上的值
        res.add(new LinkedList(track));
        return;
    }

    // 回溯算法标准框架
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.add(nums[i]);
        // 进入下一层回溯树
        backtrack(nums);
        // 取消选择
        track.removeLast();
    }
}

待选元素可能相同--且有附加要求

491. 递增子序列

q3

题目要求所有递增的子序列,且不能重复

🌰 【4,6,7(a),7(b)】 字母是为了标识相同元素

结果中可以有【4,7(a)】或 【4、7(b)】 但不能两个同时存在

借助卡哥的图分析分析:

请添加图片描

从绿色箭头往下递归前,建立map统计当前元素为开始时的使用情况,

最左边【4,7】 已经使用过一次 7

当蓝色箭头开始往下递归时,map中已经记录过7使用过,也就是以4开头,第二位置的元素使用过7,不能继续往下递归了,continue 之后继续选择下一个可以使用的元素。

关于数层去重与树枝去重,推荐看原文 :代码随想录-全排列

修订记录
2022-09-15 19:47:13 整理题型

# 算法基础 # 回溯
【Sharding-JDBC-3】分库分表策略及常见分片算法
活出生命的意义

  • 文章目录
  • 站点概览
erdengk

erdengk

91 日志
5 分类
24 标签
RSS
Github E-mail
Creative Commons
友链
  • 星球球友
  • Joey
  • 北松山(itwaix)-TP在职
  • JooKS' Blog-GSoC 2022 Mentor
  • Chever-John-Shein在职
  • 一堆网页小游戏
  • 飞鸟记
0%
© 2019 — 2025 erdengk
由 Halo 强力驱动
陕ICP备2021015348号-1
川公网安备 51011202000481号
轻点广告,请我喝水,非常感谢 (。・ω・。)ノ(*/ω\*)